Practice › Graphs
Detect Cycle in a Directed Graph
Medium · Graphs · Asked at Amazon, Microsoft, Google, Samsung
The graph is directed: each line u v is an edge from u to v. Print YES if it contains a cycle, otherwise NO.
Input
First line: n m. Next m lines: u v (1-based).
Output
YES or NO.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ m ≤ 2 · 10^5
Kahn's algorithm: repeatedly remove nodes with in-degree 0. If some nodes are never removed, there is a cycle. (DFS with a recursion-stack color works too.)
Example 1
Input
4 4 1 2 2 3 3 4 4 2
Output
YES
Example 2
Input
4 4 1 2 1 3 2 4 3 4
Output
NO
Hints
- In a DAG there is always a node with no incoming edges.
- Kahn's algorithm: repeatedly remove nodes with in-degree 0 and lower their neighbours' in-degrees. If not every node gets removed, a cycle blocks the rest.
Approach
Compute in-degrees and queue every node with in-degree 0. Pop a node, count it, and decrement the in-degree of each out-neighbour, queuing those that reach 0. Nodes on a cycle (or downstream of one) never reach in-degree 0, so if the count is less than n the graph has a cycle. A self-loop gives its node in-degree ≥ 1 forever, so it is caught too.
Complexity: O(n + m) time · O(n + m) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> adj(n + 1);
vector<int> indeg(n + 1, 0);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
indeg[v]++;
}
queue<int> q;
for (int v = 1; v <= n; v++)
if (!indeg[v]) q.push(v);
int removed = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
removed++;
for (int v : adj[u])
if (--indeg[v] == 0) q.push(v);
}
cout << (removed == n ? "NO" : "YES") << "\n";
return 0;
}Python solution
import sys
from collections import deque
data = list(map(int, sys.stdin.read().split()))
n, m = data[0], data[1]
adj = [[] for _ in range(n + 1)]
indeg = [0] * (n + 1)
for i in range(m):
u, v = data[2 + 2 * i], data[3 + 2 * i]
adj[u].append(v)
indeg[v] += 1
q = deque(v for v in range(1, n + 1) if indeg[v] == 0)
removed = 0
while q:
u = q.popleft()
removed += 1
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
print("NO" if removed == n else "YES")Java solution
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
int n = (int) in.nval;
in.nextToken();
int m = (int) in.nval;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
int[] indeg = new int[n + 1];
for (int i = 0; i < m; i++) {
in.nextToken();
int u = (int) in.nval;
in.nextToken();
int v = (int) in.nval;
adj.get(u).add(v);
indeg[v]++;
}
ArrayDeque<Integer> q = new ArrayDeque<>();
for (int v = 1; v <= n; v++) if (indeg[v] == 0) q.add(v);
int removed = 0;
while (!q.isEmpty()) {
int u = q.poll();
removed++;
for (int v : adj.get(u)) if (--indeg[v] == 0) q.add(v);
}
System.out.println(removed == n ? "NO" : "YES");
}
}Solve Detect Cycle in a Directed Graph online · All practice problems