Last Updated on March 21, 2022 by Ria Pathak

### Concepts Used

Depth First Search, Disjoint Set

### Difficulty Level

Easy

### Problem Statement :

Given an undirected graph, print Yes if a cycle is present in the graph else print No.

**See original problem statement here**

### Solution Approach :

**Introduction** :

By definition,

" Connected components in a graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph. A vertex with no incident edges is itself a component. A graph that is itself connected has exactly one component, consisting of the whole graph."This problem can be solved by many ways like

Breadth First Search,Depth First SearchorDisjoint Set. Idea is to keep count of the number of connected components. Below we are going to discuss two of the above mentioned methods to solve this problem.

**Method 1 (Using DFS)** :

In this method we are going to use

Depth First SearchorDFSto find total number of connected components. Indfs(), we are going to traverse all the adjacent vertices which are not yet visited and mark them as visited so we won’t traverse them again. We have to keep count of the differentdfs()calls made for each unvisited vertex and increment count by`1`

for each call.

We can keep track if the node is visited or not, using a booleanvisited[ ]array of size`n`

which is initially set false (why`?`

).Now the question arise, why are we counting the different calls made to

dfs()`?`

The answer lies in the fact that each time we call our dfs() function with some vertex`v`

, it marks all vertices which are connected to`v`

as visited, which means the we are visiting the vertices which are directly or indirectly connected to the`v`

and by the definition of theConnected Componentabove, this is considered as one component. So each call made up to dfs() with some unvisited vertex`v`

, gives us the different connected component.

**Method 2 (Using Disjoint Set)** :

Disjoint Set UnionorDSUdata structure is also sometimes calledUnion-Find Set. This data structure is used to keep track of the different disjoint sets.

It basically performs two operations :

Union :It takes two vertices and join them in a single set (if it is not already there).Find :Determines in which subset the element is.We will use a

`parent[]`

array to keep track of the parents of each vertex.`ith`

element will store the root/parent of i^{th}vertex. Now we will performunion()for every edge (uv) and update the`parent[]`

array.

Now, iterate for all vertices, for each vertex`v`

, we will find root of`v`

usingfind()and keep track of all distinct roots. Every time we encounter a distinct root increment the counter by`1`

.Each disjoint set stores the vertices which are connected (directly or indirectly) to each other and has no relation/connection with any other vertex (as it is non overlapping set), which means each set itself represents a connected component of the graph and since each set contains exactly one vertex as its root, the sum of distinct roots of all sets gives us the total number of connected components in the graph.

### Algorithms :

**dfs()** :

- For each call, for some vertex
`v`

( dfs(`v`

) ), we will mark the vertex`v`

as visited (`visited[v]= true`

).- Iterate for all the adjacent vertices of
`v`

and for every adjacent vertex`a`

, do following :

- if
`a`

is not visited i.e`visited[a]= false`

,- recursively call
dfs (.`a`

)

union():

- For two vertices
`u`

&`v`

, find the root for both vertices usingfind()(`a=find(u)`

&`b = find(v)`

).- If the root of
`u`

&`v`

are not similar, check the level of`a`

&`b`

as follows:

- if (
`level[a]>level[b]`

), update`parent[b] = a`

.- else , update
`parent[b]=a`

& update`level[a] = level[a]+1`

find():

- If
`(parent[v]==v)`

, returns the vertex`v`

(which is root).- Else, update
`parent[v]`

by recursively looking up the tree for the root.`(find(parent[v]))`

.

### Complexity Analysis:

The

time complexityofDepth First Searchis represented in the form of`O(V + E)`

, where`V`

is the number of nodes and`E`

is the number of edges.The

space complexityof the algorithm is`O(V)`

as it requires one array ( visited[ ]) of size`V`

.Talking about

Union-Finddata structure, since we have used path compression & union by rank (refer toDisjoint Setarticle for more detailed explanation), we will reach nearly constant time`O(1)`

for each query. It turns out, that the final amortized time complexity is`O(α(V))`

, where`α(V)`

is the inverse Ackermann function, which grows very slowly`(α(V)<5)`

. In our case a single call might take`O(logn)`

in the worst case, but if we do m such calls back to back we will end up with an average time of`O(α(n))`

.

### Solutions:

#include#include long int findd(long int parent[],int i) { if(parent[i]==i) { return i; } return parent[i] = findd(parent,parent[i]); } void unionn(long int parent[],long int level[],int i,int j) { long int a = findd(parent,i); long int b = findd(parent,j); if(level[a] < level[b]) parent[a] = b; else if(level[a] > level[b]) parent[b] = a; else { parent[b] = a; level[a]++; } } int main() { int t; scanf("%d",&t); while(t--) { int n,e; scanf("%d %d",&n,&e); long int parent[n],level[n],hash[n]; for(long int i=0;i 0) count++; } printf("%d\n",count); } return 0; }

#include <bits/stdc++.h> using namespace std; int findd(long int parent[],int i) { if(parent[i]==i) { c++; return i; } return parent[i] = findd(parent,parent[i]); } void unionn(long int parent[],long int level[],int i,int j) { long int a = findd(parent,i); long int b = findd(parent,j); if(level[a] < level[b]) parent[a] = b; else if(level[a] > level[b]) parent[b] = a; else { parent[b] = a; level[a]++; } } int main() { int t; cin>>t; while(t--) { int n,e; cin>>n>>e; long int parent[n],level[n]; for(long int i=0;i<n;i++) { parent[i]=i; level[i]=0; } while(e--) { int u,v; cin>>u>>v; unionn(parent,level,u,v); } set<long int> s; for(int i=0;i<n;i++) s.insert(findd(parent,i)); cout<<s.size()<<endl; } return 0; }

import java.util.*; class Main { int V; LinkedList[] adjListArray; int c = 0; // constructor Graph(int V) { this.V = V; // define the size of array as // number of vertices adjListArray = new LinkedList[V]; // Create a new list for each vertex // such that adjacent nodes can be stored for(int i = 0; i < V ; i++){ adjListArray[i] = new LinkedList (); } } // Adds an edge to an undirected graph void addEdge( int src, int dest) { // Add an edge from src to dest. adjListArray[src].add(dest); adjListArray[dest].add(src); } void DFSUtil(int v, boolean[] visited) { // Mark the current node as visited and print it visited[v] = true; //System.out.print(v+" "); // Recur for all the vertices // adjacent to this vertex for (int x : adjListArray[v]) { if(!visited[x]) DFSUtil(x,visited); } } int connectedComponents() { // Mark all the vertices as not visited boolean[] visited = new boolean[V]; for(int v = 0; v < V; ++v) { if(!visited[v]) { c++; DFSUtil(v,visited); } } return c; } public static void main(String[] args){ Scanner sc = new Scanner(System.in); int t = sc.nextInt(); while(t-->0) { int n = sc.nextInt(); int e = sc.nextInt(); Graph g = new Graph(n); while(e-->0) { int u = sc.nextInt(); int v = sc.nextInt(); g.addEdge(u,v); } System.out.println(g.connectedComponents()); } } }

[forminator_quiz id="1932"]

So, in this blog, we have tried to explain Depth First Search, Disjoint Set. If you want to solve interview coding questions, which are curated by our expert mentors at PrepBytes, you can follow this link interview coding.