Counting Good Components in Undirected Graph
Given an undirected graph with V vertices(numbered from 1 to V) and E edges. Find the number of good components in the graph. A component of the graph is good if and only if the component is a fully connected component.
Note: A fully connected component is a subgraph of a given graph such that there’s an edge between every pair of vertices in a component, the given graph can be a disconnected graph. Consider the adjacency list from vertices 1.
Examples:
Input:
E = 3, V = 3, adj: {{1, 2}, {1, 3}, {3, 2}}
Output: 1
Explanation: We can see that there is only one component in the graph and in this component there is a edge between any two vertces.Input:
E = 5, V = 7, adj: {{1, 2}, {7, 2}, {3, 5}, {3, 4}, {4, 5}}
Output: 2
Explanation: We can see that there are 3 components in the graph. For 1-2-7 there is no edge between 1 to 7, so it is not a fully connected component. Rest 2 are individually fully connected component.
Approach: To solve the problem follow the below idea:
If a fully connected component has n nodes then it must have (n*(n-1))/2 edges. Run DFS over the unvisited components and check if it is satisfying the condition on not.
Step-by-step approach:
- Initialize a counter variable ans to 0.
- Create a visited vector to track visited vertices.
- Iterate through all vertices (from 1 to V) and check if they are visited.
- If a vertex is not visited, perform a depth-first search to count vertices and edges in the connected component.
- Check if the component is “good” by comparing the number of edges with the expected value.
- Increment ans if the component is “good.”
Below is the implmentation of the above approach:
C++
#include <iostream> #include <vector> using namespace std; // DFS function to traverse the graph void dfs( int v, int & vertices, int & edges, vector<vector< int > >& adj, vector< int >& visited) { visited[v] = 1; // Counting the number of vertices vertices++; // Counting the number of edges edges += adj[v].size(); for ( auto to : adj[v]) { if (!visited[to]) { dfs(to, vertices, edges, adj, visited); } } } // Function to find the number of "good" // components int findNumberOfGoodComponent( int V, vector<vector< int > >& adj) { int ans = 0; vector< int > visited(V + 1, 0); for ( int i = 1; i <= V; i++) { // Check if the vertex is visited or not if (!visited[i]) { int vertices = 0, edges = 0; dfs(i, vertices, edges, adj, visited); // Checking if the component is "good" edges /= 2; if (edges == (vertices * (vertices - 1)) / 2) ans++; } } return ans; } // Drivers code int main() { // Number of vertices int V = 7; vector<vector< int > > adj(V + 1); // Add edges to the graph adj[1].push_back(2); adj[7].push_back(2); adj[3].push_back(5); adj[3].push_back(4); adj[4].push_back(5); // Find the number of "good" components int numberOfGoodComponents = findNumberOfGoodComponent(V, adj); // Output the result cout << "Number of 'good' components: " << numberOfGoodComponents << endl; return 0; } |
Java
import java.util.ArrayList; import java.util.Vector; public class GoodComponents { // DFS function to traverse the graph static void dfs( int v, int [] vertices, int [] edges, ArrayList<ArrayList<Integer> > adj, int [] visited) { visited[v] = 1 ; // Counting the number of vertices vertices[ 0 ]++; // Counting the number of edges edges[ 0 ] += adj.get(v).size(); for ( int to : adj.get(v)) { if (visited[to] == 0 ) { dfs(to, vertices, edges, adj, visited); } } } // Function to find the number of "good" components static int findNumberOfGoodComponent( int V, ArrayList<ArrayList<Integer> > adj) { int ans = 0 ; int [] visited = new int [V + 1 ]; for ( int i = 1 ; i <= V; i++) { // Check if the vertex is visited or not if (visited[i] == 0 ) { int [] vertices = { 0 }; int [] edges = { 0 }; dfs(i, vertices, edges, adj, visited); // Checking if the component is "good" edges[ 0 ] /= 2 ; if (edges[ 0 ] == (vertices[ 0 ] * (vertices[ 0 ] - 1 )) / 2 ) ans++; } } return ans; } // Drivers code public static void main(String[] args) { // Number of vertices int V = 7 ; ArrayList<ArrayList<Integer> > adj = new ArrayList<>(V + 1 ); // Initialize adjacency list for ( int i = 0 ; i <= V; i++) { adj.add( new ArrayList<Integer>()); } // Add edges to the graph adj.get( 1 ).add( 2 ); adj.get( 7 ).add( 2 ); adj.get( 3 ).add( 5 ); adj.get( 3 ).add( 4 ); adj.get( 4 ).add( 5 ); // Find the number of "good" components int numberOfGoodComponents = findNumberOfGoodComponent(V, adj); // Output the result System.out.println( "Number of 'good' components: " + numberOfGoodComponents); } } |
Python3
from collections import defaultdict # DFS function to traverse the graph def dfs(v, vertices, edges, adj, visited): visited[v] = 1 # Counting the number of vertices vertices[ 0 ] + = 1 # Counting the number of edges edges[ 0 ] + = len (adj[v]) for to in adj[v]: if not visited[to]: dfs(to, vertices, edges, adj, visited) # Function to find the number of "good" components def find_number_of_good_components(V, adj): ans = 0 visited = [ 0 ] * (V + 1 ) for i in range ( 1 , V + 1 ): # Check if the vertex is visited or not if not visited[i]: vertices = [ 0 ] edges = [ 0 ] dfs(i, vertices, edges, adj, visited) # Checking if the component is "good" edges[ 0 ] / / = 2 if edges[ 0 ] = = (vertices[ 0 ] * (vertices[ 0 ] - 1 )) / / 2 : ans + = 1 return ans # Drivers code def main(): # Number of vertices V = 7 adj = defaultdict( list ) # Add edges to the graph adj[ 1 ].append( 2 ) adj[ 7 ].append( 2 ) adj[ 3 ].extend([ 5 , 4 ]) adj[ 4 ].append( 5 ) # Find the number of "good" components number_of_good_components = find_number_of_good_components(V, adj) # Output the result print ( "Number of 'good' components:" , number_of_good_components) if __name__ = = "__main__" : main() |
C#
using System; using System.Collections.Generic; public class Program { // DFS function to traverse the graph public static void Dfs( int v, ref int vertices, ref int edges, List<List< int >> adj, List< int > visited) { visited[v] = 1; // Counting the number of vertices vertices++; // Counting the number of edges edges += adj[v].Count; foreach ( var to in adj[v]) { if (visited[to] == 0) { Dfs(to, ref vertices, ref edges, adj, visited); } } } // Function to find the number of "good" components public static int FindNumberOfGoodComponent( int V, List<List< int >> adj) { int ans = 0; List< int > visited = new List< int >( new int [V + 1]); for ( int i = 1; i <= V; i++) { // Check if the vertex is visited or not if (visited[i] == 0) { int vertices = 0, edges = 0; Dfs(i, ref vertices, ref edges, adj, visited); // Checking if the component is "good" edges /= 2; if (edges == (vertices * (vertices - 1)) / 2) ans++; } } return ans; } // Driver code public static void Main( string [] args) { // Number of vertices int V = 7; List<List< int >> adj = new List<List< int >>(V + 1); for ( int i = 0; i <= V; i++) { adj.Add( new List< int >()); } // Add edges to the graph adj[1].Add(2); adj[7].Add(2); adj[3].Add(5); adj[3].Add(4); adj[4].Add(5); // Find the number of "good" components int numberOfGoodComponents = FindNumberOfGoodComponent(V, adj); // Output the result Console.WriteLine($ "Number of 'good' components: {numberOfGoodComponents}" ); } } // This code is contributed by shivamgupta310570 |
Javascript
class GoodComponents { constructor() { this .adj = []; } dfs(v, vertices, edges, visited) { visited[v] = 1; // Counting the number of vertices vertices[0]++; // Counting the number of edges edges[0] += this .adj[v].length; for (let to of this .adj[v]) { if (visited[to] === 0) { this .dfs(to, vertices, edges, visited); } } } findNumberOfGoodComponent(V) { let ans = 0; let visited = new Array(V + 1).fill(0); for (let i = 1; i <= V; i++) { // Check if the vertex is visited or not if (visited[i] === 0) { let vertices = [0]; let edges = [0]; this .dfs(i, vertices, edges, visited); // Checking if the component is "good" edges[0] /= 2; if (edges[0] === (vertices[0] * (vertices[0] - 1)) / 2) ans++; } } return ans; } main(V, edges) { this .adj = new Array(V + 1).fill().map(() => []); // Add edges to the graph for (let edge of edges) { this .adj[edge[0]].push(edge[1]); this .adj[edge[1]].push(edge[0]); } // Find the number of "good" components let numberOfGoodComponents = this .findNumberOfGoodComponent(V); // Output the result console.log( "Number of 'good' components: " + numberOfGoodComponents); } } // Driver code new GoodComponents().main(7, [[1, 2], [7, 2], [3, 5], [3, 4], [4, 5]]); |
Number of 'good' components: 2
Time Complexity: O(V+E)
Auxiliary Space: O(depth of the graph)
Contact Us