그래프 방향 구분
무방향 사이클은 parent 간선을 제외하고, 방향 그래프 사이클은 방문 중 정점으로 돌아가는 간선을 본다.
탐색 시작점을 반복한다
모든 정점이 한 컴포넌트라는 보장이 없으면 미방문 정점마다 DFS/BFS를 시작한다.
상태 색을 사용한다
방향 그래프에서는 0/1 visited만으로는 현재 경로 안에 있는 정점을 구분하기 어렵다.
component
탐색 횟수
미방문 정점에서 새 탐색을 시작할 때마다 연결 요소가 하나
늘어난다.
격자 문제도 같은 구조다.
undirected cycle
parent 제외
방금 온 부모 간선은 사이클로 세지 않는다.
parallel edge 조건은 문제를 읽는다.
directed cycle
visiting으로 복귀
현재 재귀 스택 안의 정점으로 가는 간선이 cycle이다.
색 배열이 필요하다.
topological
DAG 전제
위상 정렬이 가능하려면 방향 사이클이 없어야 한다.
indegree 방식도 검증에 쓴다.
분리 그래프 · 방향성 · 색 초기화 점검
방향 사이클 색
// 0: unvisited, 1: visiting, 2: done
bool dfs(int v) {
color[v] = 1;
for (int to : g[v]) {
if (color[to] == 1) return true;
if (color[to] == 0 && dfs(to)) return true;
}
color[v] = 2; return false;
}