그래프 $G$에서 사이클이란 정점 $v$에서 출발하여 자기 자신으로 돌아오는 길이가 0이 아닌 경로를 말한다는 것을 다시 떠올려 봅시다. 그래프에 사이클이 없으면 그 그래프를 비순환 그래프라고 합니다.
사이클을 찾기 위해, 다음과 같은 깊이 우선 탐색의 대안적인 방법을 살펴봅시다:
void dfs(int v, int p = -1) {
for (int u : g[v])
if (u != p)
dfs(u, v);
}
여기서는 used 배열 대신, 우리가 거쳐 온 정점의 번호 또는 이 정점에서 탐색을 시작한 경우 $-1$과 같은 매개변수 $p$를 재귀에 넘깁니다.
이 방법은 트리에서만 올바르게 동작합니다. u != p 검사는 우리가 간선을 따라 되돌아가지 않도록 보장하지만, 그래프에 사이클이 있으면 어느 시점에 dfs를 같은 매개변수로 두 번째 호출하게 되어 무한 루프에 빠집니다.
무한 루프에 빠졌는지 판별할 수 있다면, 그것이 바로 우리에게 필요한 것입니다. 사이클에 진입하는 순간을 판별할 수 있도록 dfs를 수정합시다. 이를 위해 used 배열을 다시 되살리되, 이번에는 방문하려는 정점에 이전에 방문한 적이 있는지 확인하는 데 사용합니다. 방문한 적이 있다면 사이클이 존재한다는 뜻입니다.
const int maxn = 1e5;
bool used[maxn];
void dfs(int v, int p = -1) {
if (used[v]) {
cout << "Graph has a cycle" << endl;
exit(0);
}
used[v] = true;
for (int u : g[v])
if (u != p)
dfs(u, v);
}
사이클 자체를 복원해야 한다면, 프로그램을 종료하는 대신 재귀에서 여러 번 반환하면서 사이클이 발견된 정점에 도달할 때까지 정점들을 기록하면 됩니다.
// возвращает -1, если цикл не нашелся, и вершину начала цикла в противном случае
int dfs(int v, int p = -1) {
if (used[v]) {
cout << "Graph has a cycle, namely:" << endl;
return v;
}
used[v] = true;
for (int u : g[v]) {
if (u != p) {
int k = dfs(u, v);
if (k != -1) {
cout << v << endl;
if (k == v)
exit(0);
return k;
}
}
}
return -1;
}
모든 탐색이 그렇듯이, 그래프에 연결 요소가 둘 이상 있거나 그래프가 방향 그래프라면 dfs를 서로 다른 연결 요소의 정점에서 여러 번 실행해야 합니다.
for (int v = 0; v < n; v++)
if (!used[v])
dfs(v);