Practice › Graphs
Detect Cycle in an Undirected Graph
Medium · Graphs · Asked at Amazon, Microsoft, Samsung, Flipkart
Print YES if the undirected graph contains a cycle, otherwise NO. There are no self-loops or repeated edges.
Input
First line: n m. Next m lines: u v — an undirected edge (nodes are 1..n).
Output
YES or NO.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ m ≤ 2·10^5
DFS that remembers the parent, or DSU: an edge joining two nodes already in the same set closes a cycle.
Example 1
Input
5 4 1 2 2 3 3 1 4 5
Output
YES
Example 2
Input
4 3 1 2 2 3 3 4
Output
NO
Hints
- Disjoint Set Union: process edges one by one, merging the sets of their endpoints.
- If an edge connects two nodes that are already in the same set, there was another path between them — that edge closes a cycle.
Approach
Use DSU (union–find) with path compression and union by size. For each edge (u, v): if find(u) == find(v), u and v are already connected, so this edge forms a cycle. Otherwise union them. A DFS that ignores the edge back to its parent works too. The DSU version needs no recursion and handles disconnected graphs naturally.
Complexity: O((n + m) · α(n)) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
vector<int> parent, sz;
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]]; // path halving
x = parent[x];
}
return x;
}
bool unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b);
parent[b] = a;
sz[a] += sz[b];
return true;
}
int main() {
int n, m;
cin >> n >> m;
parent.resize(n + 1);
sz.assign(n + 1, 1);
iota(parent.begin(), parent.end(), 0);
bool cycle = false;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
if (!unite(u, v)) cycle = true;
}
cout << (cycle ? "YES" : "NO") << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, m = data[0], data[1]
parent = list(range(n + 1))
size = [1] * (n + 1)
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
cycle = False
for i in range(m):
a, b = find(data[2 + 2 * i]), find(data[3 + 2 * i])
if a == b:
cycle = True
break
if size[a] < size[b]:
a, b = b, a
parent[b] = a
size[a] += size[b]
print("YES" if cycle else "NO")Java solution
import java.util.*;
public class Main {
static int[] parent, sz;
static int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]]; // path halving
x = parent[x];
}
return x;
}
static boolean unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) { int t = a; a = b; b = t; }
parent[b] = a;
sz[a] += sz[b];
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
parent = new int[n + 1];
sz = new int[n + 1];
for (int i = 0; i <= n; i++) { parent[i] = i; sz[i] = 1; }
boolean cycle = false;
for (int i = 0; i < m; i++)
if (!unite(sc.nextInt(), sc.nextInt())) cycle = true;
System.out.println(cycle ? "YES" : "NO");
}
}Solve Detect Cycle in an Undirected Graph online · All practice problems