# Detect Cycle in an Undirected Graph

Posted: 24 Sep, 2020

Difficulty: Moderate

#### Given a undirected graph of V vertices and E edges. Check whether the graph contains a cycle or not. You should print "True" if the given graph contains at least one cycle, else print "False".

#### Note:

```
There are no self-loops(an edge connecting the vertice to itself) in the given graph.
```

##### Input Format:

```
The first line of input will contain three integers V, E, and S, separated by a single space.
From the second line onwards, the next 'E' lines will denote the edge of the graphs.
Every edge is defined by two single space-separated integers 'a' and 'b', which signifies an edge between vertice 'a' and vertice 'b'.
```

##### Output Format:

```
The single line contains an string, "True" if cycle exists, else "False".
```

##### Constraints:

```
1 <= V <= 10^5
0 <= E <= 2 * 10^5
0 <= u,v < V
Time Limit: 1sec
```

##### Sample Input 1:

```
4 4
0 1
1 2
2 3
3 0
```

##### Sample Output 1:

```
True
```

##### Explanation for Sample Input 1:

```
From node 0 we can reach 0 again by following this sequence of nodes in the path: 0,1,2,3,0.
Similarly from any of the node we can reach again to that node by following a path. The graph in itself is a cycle.
```

##### Sample Input 2:

```
5 3
0 1
1 2
3 4
```

##### Sample Output 2:

```
False
```

Working on approaches!

Meanwhile, please head to Code Editor and try the problem there.

Meanwhile, please head to Code Editor and try the problem there.