Undirected Graph Cycle
Undirected Graph Cycle is a medium graphs problem solved with the cycle detection pattern.
The best approach, union-find, runs in O(E · α(V)) time and O(V) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from bfs with parent tracking up.
Problem
Given an undirected graph with V vertices and a list of edges, decide whether it contains a cycle.
Examples
Example 1
- Input
V = 4, edges = [[0,1],[1,2],[2,0],[2,3]]- Output
true- Why
- 0 → 1 → 2 → 0.
Example 2
- Input
V = 4, edges = [[0,1],[1,2],[2,3]]- Output
false
Constraints
1 <= V, E <= 10^5; the graph may be disconnected.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| BFS with parent tracking | O(V + E) | O(V) |
| Union-Find | O(E · α(V)) | O(V) |
1BFS with parent tracking
O(V + E)O(V)BFS from every unvisited node, storing each node's parent. A visited neighbour that is not the parent closes a cycle.
- Queue (node, parent).
- For each neighbour: unvisited → enqueue; visited and != parent → cycle.
class Solution {
public boolean isCycle(int V, int[][] edges) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
boolean[] seen = new boolean[V];
for (int s = 0; s < V; s++) {
if (seen[s]) continue;
Queue<int[]> q = new ArrayDeque<>();
q.add(new int[] { s, -1 });
seen[s] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int v : adj.get(cur[0])) {
if (!seen[v]) { seen[v] = true; q.add(new int[] { v, cur[0] }); }
else if (v != cur[1]) return true;
}
}
}
return false;
}
}class Solution:
def isCycle(self, V: int, edges: List[List[int]]) -> bool:
adj: List[List[int]] = [[] for _ in range(V)]
for e in edges:
adj[e[0]].append(e[1])
adj[e[1]].append(e[0])
seen = [False] * V
for s in range(V):
if seen[s]:
continue
q = deque([(s, -1)])
seen[s] = True
while q:
cur = q.popleft()
for v in adj[cur[0]]:
if not seen[v]:
seen[v] = True
q.append((v, cur[0]))
elif v != cur[1]:
return True
return Falseclass Solution {
public:
bool isCycle(int V, vector<vector<int>>& edges) {
vector<vector<int>> adj(V);
for (auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); }
vector<bool> seen(V, false);
for (int s = 0; s < V; s++) {
if (seen[s]) continue;
queue<pair<int, int>> q;
q.push({s, -1});
seen[s] = true;
while (!q.empty()) {
auto cur = q.front();
q.pop();
for (int v : adj[cur.first]) {
if (!seen[v]) { seen[v] = true; q.push({v, cur.first}); }
else if (v != cur.second) return true;
}
}
}
return false;
}
};function isCycle(V, edges) {
const adj = Array.from({ length: V }, () => []);
for (const e of edges) { adj[e[0]].push(e[1]); adj[e[1]].push(e[0]); }
const seen = new Array(V).fill(false);
for (let s = 0; s < V; s++) {
if (seen[s]) continue;
const q = [[s, -1]];
let head = 0;
seen[s] = true;
while (head < q.length) {
const cur = q[head++];
for (const v of adj[cur[0]]) {
if (!seen[v]) { seen[v] = true; q.push([v, cur[0]]); }
else if (v !== cur[1]) return true;
}
}
}
return false;
}2Union-Find
O(E · α(V))O(V)Process each edge. If its two endpoints are already in the same set, this edge closes a cycle. Otherwise union them.
- parent[i] = i.
- For each edge (u, v): if find(u) == find(v) return true; else union.
class Solution {
private int[] parent;
public boolean isCycle(int V, int[][] edges) {
parent = new int[V];
for (int i = 0; i < V; i++) parent[i] = i;
for (int[] e : edges) {
int a = find(e[0]), b = find(e[1]);
if (a == b) return true;
parent[a] = b;
}
return false;
}
private int find(int x) {
while (parent[x] != x) x = parent[x] = parent[parent[x]];
return x;
}
}class Solution:
def isCycle(self, V: int, edges: List[List[int]]) -> bool:
self.parent = list(range(V))
for e in edges:
a, b = self.find(e[0]), self.find(e[1])
if a == b:
return True
self.parent[a] = b
return False
def find(self, x: int) -> int:
parent = self.parent
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return xclass Solution {
vector<int> parent;
public:
bool isCycle(int V, vector<vector<int>>& edges) {
parent.assign(V, 0);
for (int i = 0; i < V; i++) parent[i] = i;
for (auto& e : edges) {
int a = find(e[0]), b = find(e[1]);
if (a == b) return true;
parent[a] = b;
}
return false;
}
private:
int find(int x) {
while (parent[x] != x) x = parent[x] = parent[parent[x]];
return x;
}
};function isCycle(V, edges) {
const parent = new Array(V);
for (let i = 0; i < V; i++) parent[i] = i;
function find(x) {
while (parent[x] !== x) x = parent[x] = parent[parent[x]];
return x;
}
for (const e of edges) {
const a = find(e[0]), b = find(e[1]);
if (a === b) return true;
parent[a] = b;
}
return false;
}Edge cases to test
- Disconnected components (start a search from every unvisited node)
- The edge back to your parent is not a cycle
Hints
Hint 1
In DFS or BFS, reaching a visited node that is not your parent means there is a cycle.
FAQ
What is the best time complexity for Undirected Graph Cycle?
Union-Find runs in O(E · α(V)) time and O(V) extra space.
Which pattern does Undirected Graph Cycle use?
It is a graphs problem that uses the cycle detection pattern. Other problems with the same pattern: Directed Graph Cycle, Is Graph Bipartite?, Detect Cycles in 2D Grid.
Is there a brute force solution for Undirected Graph Cycle?
Yes. BFS with parent tracking takes O(V + E) time and O(V) space. BFS from every unvisited node, storing each node's parent.
Which edge cases should I test for Undirected Graph Cycle?
Disconnected components (start a search from every unvisited node); The edge back to your parent is not a cycle.