Minimum and maximum number of connected components
Given array A[] of size N representing graph with N nodes. There is an undirected edge between i and A[i] for 1 <= i <= N. The Task for this problem is to find the minimum and maximum number of connected components in the given graph if it is allowed to add an edge between any two nodes from N nodes as long as each node has a degree at most 2 in the graph.
Examples:
Input: A[] = {2, 1, 4, 3, 6, 5}
Output: 1 3
Explanation: maximum number of connected components will be 3. minimum number of connected components will be 1 since we can add edge between node pairs (2, 3) and (4, 5).
Input: A[] = {2, 3, 1, 5, 6, 4}
Output: 2 2
Explanation: maximum number of connected components will be 2 and minimum will be 2 as well since it is not possible to add edge between any two nodes.
Approach: To solve the problem follow the below observations:
Observations:
Depth-First-Search can be used to solve this problem by finding connected components.
- If any connected component is forming loop then every node of that connected component will have degree 2 (since maximum degree node can have is 2) so it is not possible to add edge between this connected component to any other connected component.
- Connected component which does not have loop will have nodes with degree less than 2 so we can add edge here with another connected component which is not forming loop. One more thing to observe is that all these connected components which does not have loop can be connected together forming single connected component thus minimizing number of connected components.
- Maximum number of connected components will not have any edge added
keeping counter for connected components with loop and without loop (let say X and Y) will be enough and the answer for maximum number of connected components will be X + Y and minimum number of connected components will be X + 1 if Y != 0 and X if Y == 0.
Below are the steps for the above approach:
- Create adjacency list for graph as adj[N + 1] and fill the adjacency table with N edges.
- Create two counters for counting with and without looped connected components as loopConnectedComponents = 0, withoutLoopConnectedComponents = 0.
- Create visited vis[N + 1] array for depth-first-search.
- Create flag = 0 which tells if current connected component during dfs call has loop or not.
- Iterate over all N nodes and call dfs function for node which is not visited yet.
- In dfs(V, parent) function mark node V visited by making vis[V] = 1
- Iterate over neighbours of V as U if it is not visited and it is not the parent node of V then call dfs function for U
- else if U is not equal to parent and parent is not -1 then mark flag as 1.
- if flag is 1 then increment in loopConnectedComponents by 1 else increment withoutLoopConnectedComponents by 1.
- Create variable as maxConnectedComponents = loopConnectedComponents + withoutLoopConnectedComponents.
- Create variable as minConnectedComponents = loopConnectedComponents and increament it by 1 if withoutLoopConnectedComponents is non zero (since we will unify all connected components without loop into one).
- print minConnectedComponents and maxConnectedComponents.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Depth first search bool dfs( int V, int parent, int & flag, vector< int >& vis, vector<vector< int > >& adj) { // Mark visited vis[V] = 1; // Iterating over V's neibours for ( auto & U : adj[V]) { // If U is not visited if (!vis[U]) { // Call dfs function for node U // with parent V dfs(U, V, flag, vis, adj); } // If U is already visited and it is // not the last node that we visited // then there is loop in connected // compoents so mark flag as 1 else if (U != parent and parent != -1) { flag = 1; } } } // Function to find minimum and maximum // connected components void findMinMaxCC( int A[], int N) { // Creating adjacency list vector<vector< int > > adj(N + 1); // Filling adjacency list for ( int i = 0; i < N; i++) { // There is undirected edge // from i to A[i] adj[i + 1].push_back(A[i]); adj[A[i]].push_back(i + 1); } // Counters for looped and without looped // connected components int loopConnectedComponents = 0, withoutLoopConnectedComponents = 0; // Creating visited array for dfs vector< int > vis(N + 1, 0); // flag to check if given connected // component has loop int flag = 0; // Iterating for all N nodes for ( int i = 1; i <= N; i++) { // If node i is not visited call dfs // for that node if (!vis[i]) { // Call dfs function dfs(i, -1, flag, vis, adj); // If flag is true increment looped // Connected component counter by 1 if (flag) loopConnectedComponents++; // If not increment without looped // connected components counter by 1 else withoutLoopConnectedComponents++; // Resetting the flag flag = 0; } } // maximum connected components int maxConnectedComponents = loopConnectedComponents + withoutLoopConnectedComponents; // Minimum connected components int minConnectedComponents = loopConnectedComponents; // Unify all connected components which // does not have loop as 1 connected component if (withoutLoopConnectedComponents != 0) minConnectedComponents++; // Printing answer of minimum and maximum // connected components cout << minConnectedComponents << " " << maxConnectedComponents << endl; } // Driver Code int32_t main() { // Input 1 int A[] = { 2, 1, 4, 3, 6, 5 }, N = 6; // Function Call findMinMaxCC(A, N); // Input 2 int A1[] = { 2, 3, 1, 5, 6, 4 }, N1 = 6; // Function Call findMinMaxCC(A1, N1); return 0; } |
Java
import java.util.ArrayList; import java.util.Arrays; public class ConnectedComponents { // Depth first search static void dfs( int V, int parent, int [] flag, int [] vis, ArrayList<ArrayList<Integer>> adj) { // Mark visited vis[V] = 1 ; // Iterating over V's neighbors for ( int U : adj.get(V)) { // If U is not visited if (vis[U] == 0 ) { // Call dfs function for node U with parent V dfs(U, V, flag, vis, adj); } // If U is already visited and it is not the last node that we visited // then there is a loop in connected components so mark flag as 1 else if (U != parent && parent != - 1 ) { flag[ 0 ] = 1 ; } } } // Function to find minimum and maximum connected components static void findMinMaxCC( int [] A, int N) { // Creating adjacency list ArrayList<ArrayList<Integer>> adj = new ArrayList<>(N + 1 ); // Filling adjacency list for ( int i = 0 ; i <= N; i++) { adj.add( new ArrayList<>()); } // Filling adjacency list for ( int i = 0 ; i < N; i++) { // There is an undirected edge from i to A[i] adj.get(i + 1 ).add(A[i]); adj.get(A[i]).add(i + 1 ); } // Counters for looped and without looped connected components int [] loopConnectedComponents = { 0 }; int [] withoutLoopConnectedComponents = { 0 }; // Creating visited array for dfs int [] vis = new int [N + 1 ]; // flag to check if the given connected component has a loop int [] flag = { 0 }; // Iterating for all N nodes for ( int i = 1 ; i <= N; i++) { // If node i is not visited call dfs for that node if (vis[i] == 0 ) { // Call dfs function dfs(i, - 1 , flag, vis, adj); // If flag is true increment looped Connected component counter by 1 if (flag[ 0 ] == 1 ) { loopConnectedComponents[ 0 ]++; } // If not increment without looped connected components counter by 1 else { withoutLoopConnectedComponents[ 0 ]++; } // Resetting the flag flag[ 0 ] = 0 ; } } // Maximum connected components int maxConnectedComponents = loopConnectedComponents[ 0 ] + withoutLoopConnectedComponents[ 0 ]; // Minimum connected components int minConnectedComponents = loopConnectedComponents[ 0 ]; // Unify all connected components which do not have a loop as 1 connected component if (withoutLoopConnectedComponents[ 0 ] != 0 ) { minConnectedComponents++; } // Printing the answer of minimum and maximum connected components System.out.println(minConnectedComponents + " " + maxConnectedComponents); } // Driver Code public static void main(String[] args) { // Input 1 int [] A = { 2 , 1 , 4 , 3 , 6 , 5 }; int N = 6 ; // Function Call findMinMaxCC(A, N); // Input 2 int [] A1 = { 2 , 3 , 1 , 5 , 6 , 4 }; int N1 = 6 ; // Function Call findMinMaxCC(A1, N1); } } |
Python
def dfs(V, parent, flag, vis, adj): # Mark visited vis[V] = 1 # Iterating over V's neighbors for U in adj[V]: # If U is not visited if not vis[U]: # Call dfs function for node U # with parent V dfs(U, V, flag, vis, adj) # If U is already visited and it is # not the last node that we visited # then there is a loop in connected # components so mark flag as 1 elif U ! = parent and parent ! = - 1 : flag[ 0 ] = 1 def findMinMaxCC(A, N): # Creating adjacency list adj = [[] for _ in range (N + 1 )] # Filling adjacency list for i in range (N): # There is an undirected edge # from i to A[i] adj[i + 1 ].append(A[i]) adj[A[i]].append(i + 1 ) # Counters for looped and without looped # connected components loopConnectedComponents = 0 withoutLoopConnectedComponents = 0 # Creating visited array for dfs vis = [ 0 ] * (N + 1 ) # Flag to check if the given connected # component has a loop flag = [ 0 ] # Iterating for all N nodes for i in range ( 1 , N + 1 ): # If node i is not visited, call dfs # for that node if not vis[i]: # Call dfs function dfs(i, - 1 , flag, vis, adj) # If flag is true, increment looped # Connected component counter by 1 if flag[ 0 ]: loopConnectedComponents + = 1 # If not, increment without looped # connected components counter by 1 else : withoutLoopConnectedComponents + = 1 # Resetting the flag flag[ 0 ] = 0 # Maximum connected components maxConnectedComponents = ( loopConnectedComponents + withoutLoopConnectedComponents ) # Minimum connected components minConnectedComponents = loopConnectedComponents # Unify all connected components which # do not have a loop as 1 connected component if withoutLoopConnectedComponents ! = 0 : minConnectedComponents + = 1 # Printing answer of minimum and maximum # connected components print (minConnectedComponents, maxConnectedComponents) # Driver Code if __name__ = = "__main__" : # Input 1 A = [ 2 , 1 , 4 , 3 , 6 , 5 ] N = 6 # Function Call findMinMaxCC(A, N) # Input 2 A1 = [ 2 , 3 , 1 , 5 , 6 , 4 ] N1 = 6 # Function Call findMinMaxCC(A1, N1) |
C#
using System; using System.Collections.Generic; public class GFG { // Depth first search static void DFS( int V, int parent, ref int flag, List< int > vis, List<List< int > > adj) { // Mark visited vis[V] = 1; // Iterating over V's neighbors foreach ( int U in adj[V]) { // If U is not visited if (vis[U] == 0) { // Call DFS function for node U with parent // V DFS(U, V, ref flag, vis, adj); } // If U is already visited and it is // not the last node that we visited, // then there is a loop in connected // components, so mark flag as 1 else if (U != parent && parent != -1) { flag = 1; } } } // Function to find minimum and maximum // connected components static void FindMinMaxCC( int [] A, int N) { // Creating adjacency list List<List< int > > adj = new List<List< int > >(); for ( int i = 0; i <= N; i++) { adj.Add( new List< int >()); } // Filling the adjacency list for ( int i = 0; i < N; i++) { // There is an undirected edge from i+1 to A[i] adj[i + 1].Add(A[i]); adj[A[i]].Add(i + 1); } // Counters for looped and without // looped connected components int loopConnectedComponents = 0; int withoutLoopConnectedComponents = 0; // Creating a visited array for DFS List< int > vis = new List< int >(); for ( int i = 0; i <= N; i++) { vis.Add(0); } // Flag to check if a given connected // component has a loop int flag = 0; // Iterating for all N nodes for ( int i = 1; i <= N; i++) { // If node i is not visited, // call DFS for that node if (vis[i] == 0) { // Call DFS function DFS(i, -1, ref flag, vis, adj); // If the flag is true, increment looped // connected component counter by 1 if (flag == 1) { loopConnectedComponents++; } // If not, increment without looped // connected components counter by 1 else { withoutLoopConnectedComponents++; } // Reset the flag flag = 0; } } // Maximum connected components int maxConnectedComponents = loopConnectedComponents + withoutLoopConnectedComponents; // Minimum connected components int minConnectedComponents = loopConnectedComponents; // Unify all connected components which // do not have a loop as 1 connected component if (withoutLoopConnectedComponents != 0) { minConnectedComponents++; } // Printing the answer of minimum and // maximum connected components Console.WriteLine(minConnectedComponents + " " + maxConnectedComponents); } public static void Main( string [] args) { // Input 1 int [] A = { 2, 1, 4, 3, 6, 5 }; int N = 6; // Function Call FindMinMaxCC(A, N); // Input 2 int [] A1 = { 2, 3, 1, 5, 6, 4 }; int N1 = 6; // Function Call FindMinMaxCC(A1, N1); } } |
Javascript
function dfs(V, parent, vis, adj, flag) { // Mark the current node as visited vis[V] = true ; // Iterate over V's neighbors for (const U of adj[V]) { if (!vis[U]) { dfs(U, V, vis, adj, flag); } // If U is already visited and it's not the parent of V // there's a loop else if (U !== parent && parent !== -1) { flag.flag = true ; } } } // Function to find minimum and // maximum connected components function GFG(A, N) { // Creating adjacency list const adj = new Array(N + 1).fill( null ).map(() => []); for (let i = 0; i < N; i++) { adj[i + 1].push(A[i]); adj[A[i]].push(i + 1); } // Counters for looped and without // looped connected components let loopConnectedComponents = 0; let withoutLoopConnectedComponents = 0; // Creating visited array for DFS const vis = new Array(N + 1).fill( false ); const flag = { flag: false }; for (let i = 1; i <= N; i++) { // If node i is not visited // call DFS for that node if (!vis[i]) { // Call DFS function dfs(i, -1, vis, adj, flag); // If flag is true, increment looped connected component counter by 1 if (flag.flag) { loopConnectedComponents++; } else { withoutLoopConnectedComponents++; } // Resetting the flag flag.flag = false ; } } // Maximum connected components const maxConnectedComponents = loopConnectedComponents + withoutLoopConnectedComponents; // Minimum connected components let minConnectedComponents = loopConnectedComponents; if (withoutLoopConnectedComponents !== 0) { minConnectedComponents++; } // Printing the answer of minimum and // maximum connected components console.log(minConnectedComponents, maxConnectedComponents); } // Driver Code ( function () { // Input 1 const A = [2, 1, 4, 3, 6, 5]; const N = 6; // Function Call GFG(A, N); // Input 2 const A1 = [2, 3, 1, 5, 6, 4]; const N1 = 6; // Function Call GFG(A1, N1); })(); |
1 3 2 2
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us