# Java program to Detect Cycle in an Undirected Graph

In this tutorial, you will learn how to detect if a cycle exists in an undirected graph in Java without using any complex cycle-detection algorithms.

## Detection of a cycle in an undirected graph in Java

What is an undirected graph?
Let`s start off by knowing what an undirected graph is, A graph in which all the nodes are connected together with bi-directional edges is called an undirected graph. For example, observe the graph below Each node in the graph is connected with the other nodes with a bi-directional edge i.e, an edge that defines the existence of a connection from Node A to B as well as Node B to A.
So in our diagram above
Node 1 is connected to 2 and Node 2 is connected to 1
Node 1 is connected to 3 and Node 3 is connected to 1
Node 2 is connected to 3 and Node 3 is connected to 2
Node 2 is connected to 1 and Node 1 is connected to 2
Node 3 is connected to 2 and Node 2 is connected to 3
Node 3 is connected to 1 and Node 1 is connected to 3

How do we represent graphs
Graphs can be represented either by adjacency matrix or by adjacency list, adjacency list is generally preferred because of its less space complexities.

Detection of cycle in an undirected graph
Since our objective is just to detect if a cycle exists or not, we will not use any cycle detection algorithm, rather we will be using a simple property between number of nodes and number of edges in a graph, we can find those out by doing a simple DFS on the graph.
For more coverage on DFS visit this link: How to perform Depth First Search in Java?
The idea being is, for every undirected cyclic graph the following property holds If the total number of nodes in the graph -1 != (The total number of components)/2 , then the graph is cyclic.

Code

```import java.io.*;
import java.util.*;
public class Solution {
//The hashset gives us the total number
//of nodes in a graph.
public static HashSet<Integer> hs;

public static int dfs(ArrayList<ArrayList<Integer>> g,int s,boolean vis[]){
//classic DFS function
int ans=g.get(s).size();
vis[s]=true;
for(int ele:g.get(s)){
//If we encounter a node
//that has not been visited
//before,we recursively call
//DFS from that node.
if(!vis[ele]){
ans+=dfs(g,ele,vis);
}
}
return ans;
}
public static void main(String[] args) throws IOException{
System.out.println("Enter the number of nodes and edges");
int n=Integer.parseInt(str);
int m=Integer.parseInt(str);
ArrayList<ArrayList<Integer>> g=new ArrayList<>();
for(int i=0;i<=n;i++){
}
System.out.println("Enter "+m+" edges");
for(int i=0;i<m;i++){
int s=Integer.parseInt(str1);
int d=Integer.parseInt(str1);
}
int cnt=0;
int vertices=0;
int edges=0;
String ans="";
boolean flag=true;
boolean vis[]=new boolean[n+1];
for(int j=1;j<=n;j++){
if(vis[j]==false){
hs=new HashSet<Integer>();
int an=dfs(g,j,vis);

//If the below property does not hold
// then cycle exists so, we set
//the flag to false
if(hs.size()-1!=an/2) flag=false;
}
}
if(flag) System.out.println("Cycle does not exist");

//If the flag is not set to false
//then cycle exists
else System.out.println("Cycle exists");
}
}
```

Output

``Enter the number of nodes and edges``
`3 3`
``Enter 3 edges``
```0 1
1 2
2 0```
``Cycle exists``

The graph looks like this The number of nodes here is 3 (0,1,2)
Number of components is 6
0–1
0–2 (2–0)
1–0 (0–1)
1–2
2–0
2–1 (1–2)

Nodes -1 == 2
Components/2 == 6/2 == 3
2 != 3
Since the property holds, we can say that a cycle exists!