# Cycle Detection in Undirected Graph using DFS

Problem Statement: Given an undirected graph with V vertices and E edges, check whether it contains any cycle or not.

Examples:

```Example 2:

Input:  Output: Cycle Detected```
```Example 2:

Input:  Output: No Cycle Detected```

### Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Approach: Run a for loop from the first node to the last node and check if the node is visited. If it is not visited then call the function recursively which goes into the depth as known as DFS search and if you find a cycle you can say that there is a cycle in the graph.

• Basically calling the isCyclic function with number of nodes and passing the graph
Traversing from 1 to number of nodes and checking for every node if it is unvisited
• If the node is unvisited then call a function checkForCycle, that checks if there is a cycle and returns true if there is a cycle.
• Now the function checkForCycle has the node and previous of the parent node. It will also have the visited array and the graph that has adjacency list
• Mark it as visited and then traverse for its adjacency list using a for loop.
• Calling DFS traversal if that node is unvisited call recursive function that checks if its a cycle and returns true
• If the previously visited node and it is not equal to the parent we can say there is cycle again and will return true
• Now if you have traveled for all adjacent nodes and all the DSF have been called and it never returned true that means we have done the DSF call entirely and now we can return false, that mean there is no DSF cycle

Code:

## C++ Code

``````#include<bits/stdc++.h>

using namespace std;

class Solution {

public:
bool checkForCycle(int node, int parent, vector < int > & vis, vector < int > adj[]) {
vis[node] = 1;
if (!vis[it]) {
return true;
} else if (it != parent)
return true;
}

return false;
}
public:
bool isCycle(int V, vector < int > adj[]) {
vector < int > vis(V + 1, 0);
for (int i = 0; i < V; i++) {
if (!vis[i]) {
if (checkForCycle(i, -1, vis, adj)) return true;
}
}

return false;
}
};

// { Driver Code Starts.
int main() {

int V = 5;
int E = 5;

Solution obj;
if (ans) {
cout << "Cycle Detected";
} else cout << "No Cycle Detected";

return 0;
}``````

Output:

Cycle Detected

Time Complexity: O(N+E),  N is the time taken and E is for traveling through adjacent nodes overall.

Space Complexity: O(N)

## Java Code

``````import java.util.*;
class GFG {
public static void main(String[] args) {

int V = 5;

ArrayList < ArrayList < Integer >> adj = new ArrayList < > ();
for (int i = 0; i < V; i++) {
}
// edge 0---1

// edge 1---2

Solution obj = new Solution();
if (ans == true) {
System.out.println("Cycle Detected");
} else {
System.out.println("No Cycle Detected");

}
}
}

class Solution {
public boolean checkForCycle(int node, int parent, boolean vis[], ArrayList < ArrayList
vis[node] = true;
if (vis[it] == false) {
if (checkForCycle(it, node, vis, adj) == true)
return true;
} else if (it != parent)
return true;
}

return false;
}
// 0-based indexing Graph
public boolean isCycle(int V, ArrayList < ArrayList < Integer >> adj) {
boolean vis[] = new boolean[V];

for (int i = 0; i < V; i++) {
if (vis[i] == false) {
return true;
}
}

return false;
}
}``````

Output:

Cycle Detected

Time Complexity: O(N+E),  N is the time taken and E is for traveling through adjacent nodes overall.

Space Complexity: O(N)