Check if each connected component has equal number of vertices and edges
Given an undirected graph with N vertices and M edges. The task for this problem is to check whether each connected component of the given graph contains an equal number of vertices and edges if it is true print “Yes” else print “No”.
Examples:
Input: N = 3, M = 3, edge[][2] = {{2, 3}, {1, 1}, {2, 3}}
Output: Yes
Explanation: This graph has two connected components:
- connected component 1 consists of 1 vertex and 1 edge so it satisfies required condition.
- connected component 2 consists of 2 vertices and 2 edges so this also satisfies required condition.
As all connected components follow above required condition hence print “Yes”.
Input: N = 5, M = 5, edge[][2] = {{1, 2}, {2, 3}, {3, 4}, {3, 5}, {1, 5}}
Output: Yes
Explanation: This graph have only one connected component, and have equal number of vertices and edges.
Approach: To solve the problem follow the below idea:
Using Depth-First-Search we can find connected components and count of edges that belongs to each component. If count of edges is equal to the number of vertices of that connected component, print yes else print no.
Follow the steps below to solve the problem:
- Initialize a variable numCnt = 1 globally to store a number of components.
- Create a vis[N] array to keep track of visited elements.
- Initialize cnt to zero to keep track of the number of vertices in the current connected component.
- Initialize components[] array which will keep track of the number of vertices in the ith connected component.
- Initialize a new array wC[] that stores which vertex belongs to which connected component.
- Call dfs() for each unvisited vertex from 1 to N.
- Iterate over all M edges and create an array edgeComponents[] that will mark the current edge belonging to which component.
- Finally, if components[] and edgeComponents[] both are equal then print “Yes” else print “No”.
Below is the code for the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Number of components counter int numCnt = 1; // dfs-function void dfs( int V, int & cnt, vector< int >& vis, vector<vector< int > >& adj, vector< int >& wC) { // Marking V as 1 vis[V] = 1; // Vertex V belongs to numCnt'th // component wC[V] = numCnt; // Incrementing the counter cnt++; // Iterate on neibhours of V for ( auto & U : adj[V]) { // If it is not visisted call // dfs for U if (!vis[U]) { dfs(U, cnt, vis, adj, wC); } } } // Function to check whether // number of edges and vertices // are equal or not in each // connected component void isPossible( int N, int edg[][2], int M) { // Creating adjacency list vector<vector< int > > adj(N + 1); // Iterating over all M edges for ( int i = 0; i < M; i++) { // There is edge from edg[i][0] // to edg[i][1] adj[edg[i][0]].push_back(edg[i][1]); // There is edge from edg[i][1] // to edg[i][0] adj[edg[i][1]].push_back(edg[i][0]); } // Visited array of dfs vector< int > vis(N + 1, 0); // cnt variable to keep count of // size of connected components int cnt = 0; // Connected components size vector< int > components; // Array of size N that stores vertex // belongs to which component vector< int > wC(N + 1, 0); // Iterating on all 1 to N vertices for ( int i = 1; i <= N; i++) { // If i is not present if (!vis[i]) { // dfs call dfs(i, cnt, vis, adj, wC); // Components array components.push_back(cnt); // Resetting counter to zero cnt = 0; // Next connected component numCnt++; } } // Array initialized of size N that // stores count of edges that // belongs to which components vector< int > edgComponent(components.size(), 0); // Iterating on all edges for ( int i = 0; i < M; i++) { edgComponent[wC[edg[i][0]] - 1]++; } // If vertex at each component are // equal to amount of edges if (edgComponent == components) cout << "Yes" << endl; else cout << "No" << endl; // Resetting number of components // back to 1 numCnt = 1; } // Driver Code int main() { // Input 1 int N = 4, M = 3; int edg[][2] = { { 1, 2 }, { 2, 3 }, { 3, 1 } }; // Function Call isPossible(N, edg, M); // Input 2 int N1 = 5, M1 = 5; int edg1[][2] = { { 1, 2 }, { 2, 3 }, { 3, 4 }, { 3, 5 }, { 1, 5 } }; // Function Call isPossible(N1, edg1, M1); return 0; } |
Java
import java.util.*; public class Main { // Number of components counter static int numCnt = 1 ; // dfs-function static void dfs( int V, int [] cnt, int [] vis, List<List<Integer> > adj, int [] wC) { // Marking V as 1 vis[V] = 1 ; // Vertex V belongs to numCnt'th component wC[V] = numCnt; // Incrementing the counter cnt[numCnt - 1 ]++; // Iterate on neighbors of V for ( int U : adj.get(V)) { // If it is not visited, call dfs for U if (vis[U] == 0 ) { dfs(U, cnt, vis, adj, wC); } } } // Function to check whether number of edges and // vertices are equal or not in each connected component static void isPossible( int N, int [][] edg, int M) { // Creating adjacency list List<List<Integer> > adj = new ArrayList<>(N + 1 ); for ( int i = 0 ; i <= N; i++) { adj.add( new ArrayList<>()); } // Iterating over all M edges for ( int i = 0 ; i < M; i++) { // There is edge from edg[i][0] to edg[i][1] adj.get(edg[i][ 0 ]).add(edg[i][ 1 ]); // There is edge from edg[i][1] to edg[i][0] adj.get(edg[i][ 1 ]).add(edg[i][ 0 ]); } // Visited array of dfs int [] vis = new int [N + 1 ]; // Array of size N that stores vertex belongs to // which component int [] wC = new int [N + 1 ]; // cnt variable to keep count of size of connected // components int [] cnt = new int [N + 1 ]; // Iterating on all 1 to N vertices for ( int i = 1 ; i <= N; i++) { // If i is not visited if (vis[i] == 0 ) { // dfs call dfs(i, cnt, vis, adj, wC); // Resetting counter to zero cnt[numCnt - 1 ] = 0 ; // Components array numCnt++; } } // Array initialized of size N that stores count of // edges that belongs to which components int [] edgComponent = new int [numCnt - 1 ]; // Iterating on all edges for ( int i = 0 ; i < M; i++) { edgComponent[wC[edg[i][ 0 ]] - 1 ]++; } // If vertex at each component are equal to amount // of edges if (!Arrays.equals( edgComponent, Arrays.copyOfRange(cnt, 0 , numCnt - 1 ))) { System.out.println( "Yes" ); } else { System.out.println( "No" ); } // Resetting number of components back to 1 numCnt = 1 ; } // Driver Code public static void main(String[] args) { // Input 1 int N = 4 , M = 3 ; int [][] edg = { { 1 , 2 }, { 2 , 3 }, { 3 , 1 } }; // Function Call // Function Call isPossible(N, edg, M); // Input 2 int N1 = 5 , M1 = 5 ; int edg1[][] = { { 1 , 2 }, { 2 , 3 }, { 3 , 4 }, { 3 , 5 }, { 1 , 5 } }; // Function Call isPossible(N1, edg1, M1); } } |
C#
using System; using System.Collections.Generic; using System.Linq; public class Gfg { // Number of components counter static int numCnt = 1; // dfs-function static void dfs( int V, ref int cnt, List< int > vis, List<List< int >> adj, List< int > wC) { // Marking V as 1 vis[V] = 1; // Vertex V belongs to numCnt'th // component wC[V] = numCnt; // Incrementing the counter cnt++; // Iterate on neibhours of V foreach ( var U in adj[V]) { // If it is not visisted call // dfs for U if (vis[U] == 0) { dfs(U, ref cnt, vis, adj, wC); } } } // Function to check whether // number of edges and vertices // are equal or not in each // connected component static void isPossible( int N, int [,] edg, int M) { // Creating adjacency list var adj = new List<List< int >>(N + 1); for ( int i = 0; i <= N; i++) { adj.Add( new List< int >()); } // Iterating over all M edges for ( int i = 0; i < M; i++) { // There is edge from edg[i][0] // to edg[i][1] adj[edg[i, 0]].Add(edg[i, 1]); // There is edge from edg[i][1] // to edg[i][0] adj[edg[i, 1]].Add(edg[i, 0]); } // Visited array of dfs var vis = new List< int >( new int [N + 1]); // cnt variable to keep count of // size of connected components int cnt = 0; // Connected components size var components = new List< int >(); // Array of size N that stores vertex // belongs to which component var wC = new List< int >( new int [N + 1]); // Iterating on all 1 to N vertices for ( int i = 1; i <= N; i++) { // If i is not present if (vis[i] == 0) { // dfs call dfs(i, ref cnt, vis, adj, wC); // Components array components.Add(cnt); // Resetting counter to zero cnt = 0; // Next connected component numCnt++; } } // Array initialized of size N that // stores count of edges that // belongs to which components var edgComponent = new List< int >( new int [components.Count]); // Iterating on all edges for ( int i = 0; i < M; i++) { edgComponent[wC[edg[i, 0]] - 1]++; } // If vertex at each component are // equal to amount of edges if (Enumerable.SequenceEqual(edgComponent, components)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); // Resetting number of components // back to 1 numCnt = 1; } public static void Main() { // Input 1 int N = 4, M = 3; int [,] edg = { { 1, 2 }, { 2, 3 }, { 3, 1 } }; // Function Call isPossible(N, edg, M); // Input 2 int N1 = 5, M1 = 5; int [,] edg1 = { { 1, 2 }, { 2, 3 }, { 3, 4 }, { 3, 5 }, { 1, 5 } }; // Function Call isPossible(N1, edg1, M1); } } |
Python3
import sys # Increase recursion limit to prevent RecursionError sys.setrecursionlimit( 10 * * 6 ) numCnt = 1 # Define depth-first search function def dfs(V, cnt, vis, adj, wC): global numCnt vis[V] = 1 wC[V] = numCnt cnt[ 0 ] + = 1 for U in adj[V]: if not vis[U]: dfs(U, cnt, vis, adj, wC) # Define function to check if a graph is a Barret graph def isPossible(N, edg, M): # Create adjacency list adj = [[] for _ in range (N + 1 )] for i in range (M): adj[edg[i][ 0 ]].append(edg[i][ 1 ]) adj[edg[i][ 1 ]].append(edg[i][ 0 ]) # Create visited list and count list vis = [ 0 ] * (N + 1 ) cnt = [ 0 ] components = [] wC = [ 0 ] * (N + 1 ) global numCnt # Iterate through all vertices to find connected components for i in range ( 1 , N + 1 ): if not vis[i]: dfs(i, cnt, vis, adj, wC) components.append(cnt[ 0 ]) cnt[ 0 ] = 0 numCnt + = 1 # Count number of edges in each component edgComponent = [ 0 ] * len (components) for i in range (M): edgComponent[wC[edg[i][ 0 ]] - 1 ] + = 1 # Check if number of edges in each component matches number of vertices in component if edgComponent = = components: print ( "Yes" ) else : print ( "No" ) numCnt = 1 # Example inputs N = 4 M = 3 edg = [[ 1 , 2 ], [ 2 , 3 ], [ 3 , 1 ]] isPossible(N, edg, M) N1 = 5 M1 = 5 edg1 = [[ 1 , 2 ], [ 2 , 3 ], [ 3 , 4 ], [ 3 , 5 ], [ 1 , 5 ]] isPossible(N1, edg1, M1) |
Javascript
// JavaScript code to implement the approach let numCnt = 1; // Define depth-first search function function dfs(V, cnt, vis, adj, wC) { vis[V] = 1; wC[V] = numCnt; cnt[0] += 1; for (let i = 0; i < adj[V].length; i++) { const U = adj[V][i]; if (!vis[U]) { dfs(U, cnt, vis, adj, wC); } } } // Define function to check if a graph is a Barret graph function isPossible(N, edg, M) { // Create adjacency list const adj = Array.from({ length: N + 1 }, () => []); for (let i = 0; i < M; i++) { adj[edg[i][0]].push(edg[i][1]); adj[edg[i][1]].push(edg[i][0]); } // Create visited list and count list const vis = new Array(N + 1).fill(0); const cnt = [0]; const components = []; const wC = new Array(N + 1).fill(0); // Iterate through all vertices to find connected components for (let i = 1; i <= N; i++) { if (!vis[i]) { dfs(i, cnt, vis, adj, wC); components.push(cnt[0]); cnt[0] = 0; numCnt += 1; } } // Count number of edges in each component const edgComponent = new Array(components.length).fill(0); for (let i = 0; i < M; i++) { edgComponent[wC[edg[i][0]] - 1] += 1; } // Check if number of edges in each component matches number of vertices in component if (edgComponent.join() === components.join()) { console.log( "Yes" ); } else { console.log( "No" ); } numCnt = 1; } // Example inputs const N = 4; const M = 3; const edg = [ [1, 2], [2, 3], [3, 1], ]; isPossible(N, edg, M); const N1 = 5; const M1 = 5; const edg1 = [ [1, 2], [2, 3], [3, 4], [3, 5], [1, 5], ]; isPossible(N1, edg1, M1); // This code is contributed by chetan bargal |
No Yes
Time Complexity: O(N + M)
Auxiliary Space: O(N)
Related Articles:
Contact Us