BOJ 23594 - Vasya's graph [C++]

 

 

문제

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

정점이 $N$개인 그래프를 구성하려 한다.

그래프 상에서 서로 이동 가능해서는 안되는 정점 쌍이 $K$개 주어지고, 그래프에 사용할 후보 간선이 $M$개 주어진다.

후보 간선들을 주어진 순서대로 하나씩 보면서, 그래프 상에 존재해도 되는 간선이면 사용하고 그렇지 않다면 그냥 넘어간다.

이 때, 사용되는 간선들을 모두 구해야 한다.

풀이

각 정점별로, 해당 정점에서 갈 수 있는 정점들의 목록 $V$와, 해당 정점으로부터 도달해서는 안되는 정점의 목록 $S$를 정의하고 관리해보자.

 

후보 간선들 중, 현재 보고있는 간선을 $(a,b)$라고 하자.

정점 $a$와 $b$가 그래프 상에서 이미 서로에게 도달 가능한 상태이면, 해당 간선은 당연히 사용 가능하다.

그렇지 않다면, 이 간선을 추가했을 때 $V[a]$에 존재하는 어떤 점 $x$가 $S[b]$에도 존재한다면, 문제 조건에 위배되기 때문에 이 간선은 사용할 수 없다.

마찬가지로, $V[b]$에 존재하는 어떤 점 $y$가 $S[a]$에도 존재한다면 이 간선은 사용할 수 없다.

그렇지 않다면, 간선을 사용할 수 있으므로 잘 보관해놓고 있자.

 

정리하면, 해결해야 하는 부분이 두 가지 있다.

 

1. 정점 $a$와 $b$가 그래프 상에서 서로 도달 가능한 상태인지 확인하기

$\rightarrow$ 분리 집합으로 판별할 수 있다.

 

2. $V$와 $S$ 관리하기

$\rightarrow$ 어차피 간선 $(a,b)$에 대해 분리 집합으로 각자의 루트만 가져올거면, 같은 집합에 속하는 정점들 끼리는 모두 $V$와 $S$가 같기 때문에 여러 개를 관리할 필요가 없어진다. union할 때 smaller to larger로 $V$와 $S$를 집합의 루트가 될 정점에게 쥐어주면 된다.

 

#include <iostream>
#include <set>
#include <functional>
using namespace std;

set<int> S[100001]{};
vector<int> V[100001]{};
int r[100001]{};

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int N, K, M;
    cin >> N >> K >> M;
    for (int i = 1; i <= N; i++) V[i].push_back(i), r[i] = i;
    function<int(int)> f = [&](int x) -> int { return x == r[x] ? x : r[x] = f(r[x]); };

    for (int a,b; K--;) {
        cin >> a >> b;
        S[a].insert(b);
        S[b].insert(a);
    }

    vector<int> ans;
    for (int a, b, i = 1; M--; i++) {
        cin >> a >> b;
        int x = f(a), y = f(b);
        if (x == y) {
            ans.push_back(i);
            continue;
        }
        bool flag = 1;
        int small = V[x].size() < V[y].size() ? x : y;
        int big = small == x ? y : x;
        for (int k : V[small]) {
            if (S[big].count(k)) { flag = 0; break; }
        }
        if (!flag) continue;

        ans.push_back(i);
        if (V[x].size() > V[y].size()) swap(V[x], V[y]);
        for (int k : V[x]) V[y].push_back(k);
        V[x] = vector<int>();
        if (S[x].size() > S[y].size()) swap(S[x], S[y]);
        for (int k : S[x]) S[y].insert(k);
        S[x] = set<int>();
        r[x] = y;

    }
    cout << ans.size() << '\n';
    for (int i : ans) cout << i << ' ';

}