[백준] 25030번: 양분

📌 문제

https://www.acmicpc.net/problem/20530

📌 설명

사이클에 속하는 노드를 루트 노드로 하여 새로운 트리를 만든다. 만약 두 노드가 하나의 트리에 존재한다면 단순 경로의 수는 1, 다른 트리에 존재한다면 2이다.

먼저 DFS를 통해 사이클을 탐지하고 해당하는 노드들을 찾는다. 연결된 두 노드에 대하여 만약 한 노드가 사이클에 속한 노드라면 다른 노드의 부모를 사이클에 속한 노드로 설정한다. 두 노드가 같은 트리에 속하는지는 둘의 부모 노드를 살펴봄으로써 알 수 있다. 언급한 내용들을 구현하기 위해 Union-Find 알고리즘을 사용한다.

📌 코드

#include <iostream>
#include <vector>

using namespace std;
int n, q;
vector<int> v[200001];
int cycle[200001];
int visited[200001];
int parent[200001];
bool findCycle;

// 사이클 발견 및 해당 노드 찾기
void dfs(int s, int p) {
    visited[s] = 1;
    parent[s] = p;
    for (int next : v[s]) {
        if (!visited[next]) {
            dfs(next, s);
        }
        // 사이클 발생
        else if (next != p && !findCycle) {
            findCycle = true;
            int cur = s;
            cycle[next] = 1;
            while (cur != next) {
                cycle[cur] = 1;
                cur = parent[cur];
            }
            return;
        }

        if (findCycle) return;
    }
}

int Find(int n) {
    if (n == parent[n]) return n;
    return parent[n] = Find(parent[n]);
}

// 사이클에 속한 노드가 루트 노드가 되도록 합쳐야 한다.
void Union(int x, int y) {
    int px = Find(x);
    int py = Find(y);

    if (cycle[px] && cycle[py])
        return;
    else if (cycle[px])
        parent[py] = px;
    else if (cycle[py])
        parent[px] = py;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    // 초기화
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }

    // 사이클에 속한 노드들을 루트 노드로 하여 각각의 트리로 분할한다.
    // 두 노드가 다른 트리에 있다면 2, 같은 트리에 있다면 1
    dfs(1, -1);

    for (int i = 1; i <= n; i++) {
        if (cycle[i])
            parent[i] = i;
    }


    for (int i = 1; i <= n; i++) {
        for (int next : v[i]) {
            if (Find(i) != Find(next)) {
                Union(i, next);
            }
        }
    }

    for (int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        if (Find(x) == Find(y)) {
            cout << "1\n";
        }
        else {
            cout << "2\n";
        }
    }
}