그래프에서 사이클 찾기

사이클(Cycle) 이란

그래프에서 사이클은 한 정점에서 시작하여 어떤 경로를 지나 다시 그 정점으로 돌아오는 경로를 말한다. 유향, 무향 그래프에서 사이클을 찾는 방법을 알아보자.

유향 그래프에서 사이클 찾기

유향 그래프에서 사이클은 DFS를 사용해 찾을 수 있다. DFS 수행 중 역행 간선이 있다면 그래프 내 사이클이 있다고 판별할 수 있다.

방향 그래프

#include <bits/stdc++.h>
using namespace std;

int visited[10];
vector<int> adj[10];
bool dfs(int here) {
    visited[here] = 1;
    for(int& there : adj[here]) {
        if(visited[there]) return true;
        if(dfs(there)) return true;
    }
    return false;
}
int main() {
    for(int i = 1; i <= 8; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }
    cout << (dfs(1) ? "O" : "X");
    return 0;
}

무향 그래프에서 사이클 찾기

무향 그래프에서 사이클은 유니온 파인드를 이용해 찾을 수 있다. 이 방법은 MST를 찾는 크루스칼 알고리즘에서 사용되는 방법이기도 하다. 합치려는 정점 u, v가 같은 집합에 있다면 u, v로 이루어진 사이클이 있는 것으로 볼 수 있다.

#include <bits/stdc++.h>
using namespace std;

int parent[10];
bool cycle;
vector<pair<int, int>> edges;
int find(int u) {
    if(u == parent[u]) return parent[u];
    return parent[u] = find(parent[u]);
}
bool merge(int u, int v) {
    u = find(u);
    v = find(v);
    if(u == v) return false;
    parent[v] = u;
    return true;
}
int main() {
    for(int i = 1; i <= 8; i++) {
        int u, v;
        cin >> u >> v;
        edges.emplace_back(u ,v);
    }
    iota(parent, parent + 10, 0);
    for(auto& [u, v] : edges) {
        if(merge(u, v) == false) cycle = true;
    }
    cout << (cycle ? "YES" : "NO");
    return 0;
}