Cycle Detection: 그래프 사이클 탐지

Cycle Detection, 사이클 탐지, cycle finding

정의

그래프에 사이클이 존재하는가, 또는 어느 사이클인가 를 찾는 문제.

무향 그래프

Union-Find 접근

간선 (u, v) 삽입 시 find(u) == find(v) 이면 사이클.

DSU dsu(n);
for (auto [u, v] : edges) {
    if (dsu.same(u, v)) { /* 사이클! */ }
    else dsu.merge(u, v);
}

DFS 접근

부모가 아닌 방문 완료 정점으로 되돌아가면 사이클.

유향 그래프

DFS + 3 색

• 흰색: 미방문
• 회색: DFS 스택 위
• 검은색: 완료 회색 정점으로 가는 간선 = back edge = 사이클.

vector<int> color;  // 0/1/2

bool dfs(int u, vector<vector<int>>& adj) {
    color[u] = 1;
    for (int v : adj[u]) {
        if (color[v] == 1) return true;              // back edge
        if (color[v] == 0 && dfs(v, adj)) return true;
    }
    color[u] = 2;
    return false;
}

Kahn’s 활용

위상 정렬 로 얻은 순서 크기 < N 이면 사이클 존재.

참고

• Topological Sorting
• Union-Find
• Tarjan SCC (강한 연결 요소)