백준 20530 - 양분

noj.am/20530

풀이

문제에 언급된 그래프는 다음과 같은 모양을 가질 수 있다.

 

이들의 공통점은 사이클이 하나 존재한다는 것이다.

 

따라서 단순 경로의 갯수는 u에서 v로 가다가 두갈래 길을 만나냐 만나지 않느냐로 갈린다. 따라서 오직 2와 1만 답이 될 수 있다.

 

두갈래로 나뉘는지 아닌지 어떻게 알 수 있을까?

 

만약 두 노드가 사이클을 경유하지 않으면 1이다. 길이 하나만 있을 수 밖에 없다.

 

두 노드가 사이클을 경유하는 경우를 살펴보자.

 

두 노드가 사이클에 속한 경우는 무조건 두 갈래로 탐색할 수 있기 때문에 2이다.

 

두 노드가 사이클에 속하지 않은 경우도 2다. 탐색하다 사이클을 만나 두갈래로 나눠지기 때문이다.

 

한 노드만 사이클에 속한 경우는 조금 복잡하다. 다음 그래프를 보자.

 

다음 그래프에서 한 노드만 사이클에 속할 때 경로의 개수가 1인 경우는 3번 노드를 택한 경우이다.

 

사이클에 속하지 않는 노드가 5번, 6번인걸 고려할 때 3번 노드를 살펴보면 재미있는 걸 발견할 수 있다.

 

3번 노드는 노드 5와 6이 탐색하다가 처음 마주치는 사이클이다.

 

이 발견을 가지고 이렇게 정리할 수 있을 것이다.

 

노드 a, b가 있고 a는 사이클에 속하지 않고 b는 사이클에 속한다고 할 때 a가 탐색하면서 처음으로 만난 사이클 노드가 b이면 경로의 개수는 1이다.

 

그런데 이 경우들을 각 쿼리마다 탐색하면 TLE를 받을 게 뻔하다.

 

우리는 그래프를 이런 식으로 바라볼 수 있다.

각 사이클에 속한 노드를 트리의 루트라 생각하고 그에 연결된 노드들을 자식으로 생각하는 것이다.

 

그래프를 포레스트라 간주할 수 있고 문제를 이렇게 바꿀 수 있다.

 

두 노드 u와 v가 모두 사이클에 속하거나 LCA(최소 공통 조상)가 다르면 2, 그렇지 않으면 1을 출력하라.

 

한 노드만 사이클에 속한 경우 LCA가 같으면 사이클에 속하지 않은 노드에서 시작해 처음 만나는 사이클 노드가 트리의 루트가 되기 때문에 이 루트가 같냐 다르냐에 따라 단순 경로의 개수를 결정할 수 있는 것이다.

 

우리는 사이클에 속하는 노드를 저장하고 이 노드를 루트 삼아 만들어진 트리의 LCA를 저장해주는 과정을 거친후 각 쿼리에 알맞은 답을 출력하면 된다.

구현

구현에는 DFS를 통해 무향 그래프의 사이클을 저장하고 BFS로 LCA를 저장했다.

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> tree[200001];
bool discovered[200001];
bool finished[200001];
int backward[200001];
unordered_set<int> cycle;
int mobile[200001];
int from, last;
int n, q;
 
void dfs(int cur, int par);
void bfs(int node);
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> n >> q;
 
    int stt;
 
    for (int i = 0; i < n; ++i)
    {
        int go, to;
        cin >> go >> to;
        stt = go;
 
        tree[go].push_back(to);
        tree[to].push_back(go);
    }
 
    dfs(stt, 0);
 
    while (1)
    {
        cycle.insert(last);
        if (last == from) break;
        last = backward[last];
    }
 
    memset(discovered, 0, sizeof discovered);
    for (int v: cycle)
        if (!discovered[v])
            bfs(v);
 
    while (q--)
    {
        int u, v;
        cin >> u >> v;
 
        if (cycle.count(u) && cycle.count(v))
            cout << "2\n";
        else if (mobile[u] != mobile[v])
            cout << "2\n";
        else
            cout << "1\n";
    }
}
 
void dfs(int cur, int par)
{
    discovered[cur] = true;
 
    for (int x: tree[cur])
    {
        if (!discovered[x])
        {
            backward[x] = cur;
            dfs(x, cur);
        }
        else if (!finished[x] && x != par)
            from = x, last = cur;
    }
 
    finished[cur] = true;
}
 
void bfs(int node)
{
    queue<int> q;
 
    q.push(node);
 
    while (q.size())
    {
        int cur = q.front();
        q.pop();
 
        discovered[cur] = true;
        mobile[cur] = node;
 
        for (int next: tree[cur])
        {
            if (cycle.count(next) || discovered[next])
                continue;
            
            q.push(next);
        }
    }
}
 

아무리 봐도 골드 3에 있을 문제는 아니다.