Dado un grafo no dirigido que consta de N vértices y M aristas y una array edge [][] , en la que cada fila representa dos vértices conectados por una arista, la tarea es encontrar el grado mínimo de tres Nodes que forman un triángulo en el gráfico . Si no existe ningún triángulo en el gráfico , imprima «-1» .
Ejemplos:
Entrada: N = 7, Bordes = [[1, 2], [1, 3], [2, 3], [1, 4], [2, 5], [2, 7], [3, 6] , [3, 7]]
Salida: 4
Explicación: A continuación se muestra la representación del gráfico anterior:
Hay dos triángulos conectados:
- Uno formado por los Nodes {1, 2, 3}. Grado del triángulo = 5.
- Segundo triángulo formado por los Nodes {2, 3, 7}. Grado del triángulo = 4.
El grado mínimo es 4.
Entrada: N = 6, Bordes = [[1, 2], [1, 3], [2, 3], [1, 6], [3, 4], [4, 5]]
Salida: 2
Enfoque: El problema dado se puede resolver encontrando el grado de cada triplete de Nodes que forman un triángulo y contando el grado de cada Node en ese triángulo. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos ans como INT_MAX que almacene el grado mínimo de Nodes que forman un triángulo.
- Cree una array de adyacencia a partir del conjunto de aristas dado .
- Almacena el grado de cada Node del gráfico dado en una array auxiliar , por ejemplo, grado[] .
- Ahora, itere para todos los posibles tripletes de Nodes (i, j, k) sobre el rango [1, N] y realice los siguientes pasos:
- Si hay aristas entre cada par de tripletes , entonces existe un triángulo. Por lo tanto, actualice el valor de ans como el mínimo de ans y (grado[i] + grado[j] + grado[k] – 6) .
- De lo contrario, continúe con la siguiente iteración .
- Después de completar los pasos anteriores, si el valor es INT_MAX , imprima » -1″ . De lo contrario, imprima el valor de ans como el grado mínimo de cualquier triángulo en el gráfico.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum degree
// of a connected triangle in the graph
int minTrioDegree(int N,
vector<vector<int> >& Edges)
{
// Store the degree of each node
// in the graph
int degree[N + 1] = { 0 };
// Stores the representation of
// graph in an adjancency matrix
int adj[N + 1][N + 1] = { 0 };
// Create the adjacency matrix and
// count the degree of nodes
for (int i = 0; i < Edges.size(); i++) {
// u & v are the endpoint of
// the ith edge
int u = Edges[i][0];
int v = Edges[i][1];
// Mark both edges i.e.,
// edge u->v and v->u
adj[u][v] = adj[u][v] = 1;
// Increment degree by 1
// of both endnodes
degree[u]++;
degree[v]++;
}
// Stores the required result
int ans = INT_MAX;
// Traverse for the first node
for (int i = 1; i <= N; i++) {
// Traverse for the second node
for (int j = i + 1; j <= N; j++) {
// If there is an edge between
// these two nodes
if (adj[i][j] == 1) {
// Traverse all possible
// third nodes
for (int k = j + 1;
k <= N; k++) {
// If there is an edge
// between third node
// and the previous two
if (adj[i][k] == 1
&& adj[j][k] == 1) {
// Update ans
ans = min(ans,
degree[i]
+ degree[j]
+ degree[k] - 6);
}
}
}
}
}
// Return the result
return ans == INT_MAX ? -1 : ans;
}
// Driver Code
int main()
{
vector<vector<int> > Edges;
Edges = { { 1, 2 }, { 1, 3 },
{ 2, 3 }, { 1, 4 },
{ 2, 5 }, { 2, 7 },
{ 3, 6 }, { 3, 7 } };
int N = 7;
cout << minTrioDegree(N, Edges);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the minimum degree
// of a connected triangle in the graph
static int minTrioDegree(int N,int [][]Edges)
{
// Store the degree of each node
// in the graph
int degree[] = new int[N + 1];
// Stores the representation of
// graph in an adjancency matrix
int adj[][] = new int[N + 1][N + 1];
// Create the adjacency matrix and
// count the degree of nodes
for (int i = 0; i < Edges.length; i++) {
// u & v are the endpoint of
// the ith edge
int u = Edges[i][0];
int v = Edges[i][1];
// Mark both edges i.e.,
// edge u.v and v.u
adj[u][v] = adj[u][v] = 1;
// Increment degree by 1
// of both endnodes
degree[u]++;
degree[v]++;
}
// Stores the required result
int ans = Integer.MAX_VALUE;
// Traverse for the first node
for (int i = 1; i <= N; i++) {
// Traverse for the second node
for (int j = i + 1; j <= N; j++) {
// If there is an edge between
// these two nodes
if (adj[i][j] == 1) {
// Traverse all possible
// third nodes
for (int k = j + 1;
k <= N; k++) {
// If there is an edge
// between third node
// and the previous two
if (adj[i][k] == 1
&& adj[j][k] == 1) {
// Update ans
ans = Math.min(ans,
degree[i]
+ degree[j]
+ degree[k] - 6);
}
}
}
}
}
// Return the result
return ans == Integer.MAX_VALUE ? -1 : ans;
}
// Driver Code
public static void main(String[] args)
{
int [][]Edges = { { 1, 2 }, { 1, 3 },
{ 2, 3 }, { 1, 4 },
{ 2, 5 }, { 2, 7 },
{ 3, 6 }, { 3, 7 } };
int N = 7;
System.out.print(minTrioDegree(N, Edges));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach import sys # Function to find the minimum degree # of a connected triangle in the graph def minTrioDegree(N, Edges): # Store the degree of each node # in the graph degree = [0] * (N+1) # Stores the representation of # graph in an adjancency matrix adj = [] for i in range(0, N+1): temp = [] for j in range(0, N+1): temp.append(0) adj.append(temp) # Create the adjacency matrix and # count the degree of nodes for i in range(len(Edges)): # u & v are the endpoint of # the ith edge u = Edges[i][0] v = Edges[i][1] # Mark both edges i.e., # edge u->v and v->u adj[u][v] = adj[u][v] = 1 # Increment degree by 1 # of both endnodes degree[u] += 1 degree[v] += 1 # Stores the required result ans = sys.maxsize # Traverse for the first node for i in range(1, N+1, 1): # Traverse for the second node for j in range(i + 1, N+1, 1): # If there is an edge between # these two nodes if adj[i][j] == 1: # Traverse all possible # third nodes for k in range(j + 1, N+1, 1): # If there is an edge # between third node # and the previous two if (adj[i][k] == 1) and (adj[j][k] == 1): # Update ans ans = min(ans, degree[i] + degree[j] + degree[k] - 6) # Return the result if ans == sys.maxsize: return -1 return ans # Driver Code Edges = [[1, 2], [1, 3], [2, 3], [1, 4], [2, 5], [2, 7], [3, 6], [3, 7]] N = 7 print(minTrioDegree(N, Edges)) # This code is contributed by Dharanendra L V.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to find the minimum degree
// of a connected triangle in the graph
static int minTrioDegree(int N, int [,]Edges)
{
// Store the degree of each node
// in the graph
int []degree = new int[N + 1];
// Stores the representation of
// graph in an adjancency matrix
int [,]adj = new int[N + 1, N + 1];
// Create the adjacency matrix and
// count the degree of nodes
for (int i = 0; i < Edges.GetLength(0); i++)
{
// u & v are the endpoint of
// the ith edge
int u = Edges[i, 0];
int v = Edges[i, 1];
// Mark both edges i.e.,
// edge u.v and v.u
adj[u, v] = adj[u, v] = 1;
// Increment degree by 1
// of both endnodes
degree[u]++;
degree[v]++;
}
// Stores the required result
int ans = int.MaxValue;
// Traverse for the first node
for (int i = 1; i <= N; i++) {
// Traverse for the second node
for (int j = i + 1; j <= N; j++) {
// If there is an edge between
// these two nodes
if (adj[i,j] == 1) {
// Traverse all possible
// third nodes
for (int k = j + 1;
k <= N; k++) {
// If there is an edge
// between third node
// and the previous two
if (adj[i,k] == 1
&& adj[j,k] == 1) {
// Update ans
ans = Math.Min(ans,
degree[i]
+ degree[j]
+ degree[k] - 6);
}
}
}
}
}
// Return the result
return ans == int.MaxValue ? -1 : ans;
}
// Driver Code
public static void Main(String[] args)
{
int [,]Edges = { { 1, 2 }, { 1, 3 },
{ 2, 3 }, { 1, 4 },
{ 2, 5 }, { 2, 7 },
{ 3, 6 }, { 3, 7 } };
int N = 7;
Console.Write(minTrioDegree(N, Edges));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript program for the above approach
// Function to find the minimum degree
// of a connected triangle in the graph
function minTrioDegree(N,Edges)
{
// Store the degree of each node
// in the graph
var degree = Array.from({length: N+1}, (_, i) => 0);
// Stores the representation of
// graph in an adjancency matrix
var adj = Array(N+1).fill(0).map(x => Array(N+1).fill(0));
// Create the adjacency matrix and
// count the degree of nodes
for (var i = 0; i < Edges.length; i++) {
// u & v are the endpovar of
// the ith edge
var u = Edges[i][0];
var v = Edges[i][1];
// Mark both edges i.e.,
// edge u.v and v.u
adj[u][v] = adj[u][v] = 1;
// Increment degree by 1
// of both endnodes
degree[u]++;
degree[v]++;
}
// Stores the required result
var ans = Number.MAX_VALUE;
// Traverse for the first node
for (var i = 1; i <= N; i++) {
// Traverse for the second node
for (var j = i + 1; j <= N; j++) {
// If there is an edge between
// these two nodes
if (adj[i][j] == 1) {
// Traverse all possible
// third nodes
for (var k = j + 1;
k <= N; k++) {
// If there is an edge
// between third node
// and the previous two
if (adj[i][k] == 1
&& adj[j][k] == 1) {
// Update ans
ans = Math.min(ans,
degree[i]
+ degree[j]
+ degree[k] - 6);
}
}
}
}
}
// Return the result
return ans == Number.MAX_VALUE ? -1 : ans;
}
// Driver Code
var Edges = [ [ 1, 2 ], [ 1, 3 ],
[ 2, 3 ], [ 1, 4 ],
[ 2, 5 ], [ 2, 7 ],
[ 3, 6 ], [ 3, 7 ] ];
var N = 7;
document.write(minTrioDegree(N, Edges));
// This code is contributed by 29AjayKumar
</script>
Producción:
4
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por sumukh_bhardwaj y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA