Given an undirected graph consisting of N vertices and M edges and an array edges[][], with each row representing two vertices connected by an edge, the task is to find the minimum degree of three nodes forming a triangle in the graph. If there doesn’t exist any triangle in the graph, then print “-1”.
Examples:
Input: N = 7, Edges = [[1, 2], [1, 3], [2, 3], [1, 4], [2, 5], [2, 7], [3, 6], [3, 7]]
Output: 4
Explanation: Below is the representation of the above graph:
There are two connected triangles:
- One formed by nodes {1, 2, 3}. Degree of the triangle = 5.
- Second triangle formed by nodes {2, 3, 7}. Degree of the triangle = 4.
The minimum degree is 4.
Input: N = 6, Edges = [[1, 2], [1, 3], [2, 3], [1, 6], [3, 4], [4, 5]]
Output: 2
Approach: The given problem can be solved by finding the degree of every triplet of nodes forming a triangle and count the degree of each node in that triangle. Follow the steps below to solve the problem:
- Initialize a variable, say ans as INT_MAX that stores the minimum degree of nodes forming a triangle.
- Create an adjacency matrix from the given set of edges.
- Stores the degree of each node of the given graph in an auxiliary array, say degree[].
- Now, iterate for all possible triplets of nodes (i, j, k) over the range [1, N] and perform the following steps:
- If there are edges between each pair of triplets, then there exists a triangle. Therefore, update the value of ans as the minimum of ans and (degree[i] + degree[j] + degree[k] – 6).
- Otherwise, continue to the next iteration.
- After completing the above steps, if the value ans is INT_MAX, then print “-1”. Otherwise, print the value of ans as the minimum degree of any triangle in the graph.
Below is the implementation of the above approach:
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 graphint 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 Codeint 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 approachimport java.util.*;class GFG{// Function to find the minimum degree// of a connected triangle in the graphstatic 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 Codepublic 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 approachimport sys# Function to find the minimum degree# of a connected triangle in the graphdef 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 CodeEdges = [[1, 2], [1, 3], [2, 3], [1, 4], [2, 5], [2, 7], [3, 6], [3, 7]]N = 7print(minTrioDegree(N, Edges))# This code is contributed by Dharanendra L V. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{// Function to find the minimum degree// of a connected triangle in the graphstatic 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 Codepublic 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 graphfunction 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 Codevar 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> |
Output:
4
Time Complexity: O(N3)
Auxiliary Space: O(N2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
