백준19862 Koosaga's Problem

작성일 | In

문제 링크

  • http://icpc.me/19862

문제 출처

  • :)

사용 알고리즘

  • 랜덤 해싱
  • DFS 트리

시간복잡도

  • $O(N+M \log M)$

풀이

정해(출제자가 의도한 풀이)는 엄청 복잡한 것으로 알고 있는데, 재밌고 간단한 랜덤 풀이가 있다고 해서 공부해봤습니다.


주어진 그래프의 DFS 트리를 만들어봅시다. DFS Tree의 검은색 간선은 Tree Edge, 빨간색과 갈색 간선은 Back Edge입니다.
트리에서 깊이가 짝수인 정점과 홀수인 정점을 각각 노란색과 초록색으로 칠한다면, 문제에서 요구하는 간선 집합 $S$에 들어갈 간선은 동일한 색을 잇는 간선들입니다. 즉, 서로 다른 색의 정점을 잇는 갈색 간선은 신경 쓸 필요가 없습니다.


이분 그래프가 되기 위해서는 홀수 사이클이 없어야 하므로, 위 그림과 같은 홀수 사이클이 있으면 간선 하나를 끊어주고 색깔을 다시 잘 칠해주면 됩니다. 간선을 최소한으로 끊어서 홀수 사이클을 없애는 문제입니다.


홀수 사이클에 속한 간선에 태그를 붙여봅시다. 첫 번째 사이클(빨간색 사이클)에 속하는 간선에는 A라는 태그를, 두 번째 사이클(보라색 사이클)에 속하는 간선은 B라는 태그를 붙일 것 입니다. 그래프에 여러 종류의 태그가 붙어있을텐데, 각 태그가 달려있는 간선을 한 번씩 제거해주면 됩니다.
간선에 태그를 다 붙여준 뒤 간선 집합 $S$의 크기가 0, 1, 2일 때를 나눠서 풀이를 알아봅시다.

|S| = 0이 되는 경우

만약 그래프의 간선에 붙은 태그의 종류가 0가지라면 이미 이분 그래프이기 때문에 $|S| = 0$입니다. 1을 출력해주면 됩니다.

|S| = 1이 되는 경우

그래프에 여러 개의 태그가 붙어있고, 그 태그들의 집합을 T = {T_1, T_2, …, T_k}라고 합시다. 만약 $k$개의 태그가 모두 붙어있는 간선이 존재한다면, 그 간선 하나만 제거해주면 이분그래프가 됩니다.
$k$개의 태그가 모두 붙어있는 간선의 개수가 문제의 정답이 됩니다.

|S| = 2가 되는 경우

어떤 간선 $e$에 붙어있는 태그가 $A \subset T$이고, 다른 간선 $e’$에 붙어있는 태그가 $T \setminus A$라면 $e$와 $e’$을 제거해서 이분 그래프를 만들 수 있습니다. 이런 $(e, e’)$ 쌍의 개수를 찾아주면 됩니다.

구현

태그가 최대 $O(M)$가지 존재할 수 있기 때문에 태그 집합을 실제로 관리하는 것은 힘듭니다. $|S| = 2$인 경우를 처리할 때 차집합을 구해야하기 때문에 차집합을 빠르게 표현할 수 있는 방법을 사용해야 합니다.

태그를 임의의 정수로 표현하고, 태그들의 집합은 정수를 xor한 값으로 관리하는 방법을 생각해볼 수 있습니다. 비트가 우연히 겹쳐서 xor한 값이 0이 되는 것을 막기 위해 64bit의 랜덤한 정수를 생성해 사용할 것입니다.
그래프에 존재하는 모든 태그를 xor한 값과 태그의 부분집합의 등장 횟수를 std::map같은 자료구조로 저장해두면 unordered_map의 경우 $O(N+M)$, map의 경우에는 $O(N+M \log M)$에 문제를 풀 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
const int WHITE = 0, GRAY = 1, BLACK = 2;

int n, m, chk[202020], color[202020];
vector<int> g[202020];
map<ll, ll> cnt;
ll xor_val[202020], xor_all, ans;
mt19937_64 rd(0x917917);

void dfs(int v, int b = -1){
    chk[v] = GRAY;
    for(auto i : g[v]) if(i == b) {
        if(chk[i] == WHITE){
            color[i] = !color[v]; dfs(i, v);
            xor_val[v] ^= xor_val[i];
        }
        if(chk[i] == GRAY){
            ll t = rd();
            xor_val[v] ^= t; xor_val[i] ^= t; cnt[t]++;
            if(color[v] == color[i]) xor_all ^= t;
        }
    }
    chk[v] = BLACK;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m;
    for(int i=0; i<m; i++){
        int s, e; cin >> s >> e;
        g[s].push_back(e); g[e].push_back(s);
    }
    dfs(1);
    for(int i=2; i<=n; i++) cnt[xor_val[i]]++;

    if(!xor_all) ans = 1;
    else if(cnt.count(xor_all)) ans = cnt[xor_all];
    else {
        for(auto i : cnt) if(cnt.count(xor_all ^ i.x)) ans += i.y * cnt[xor_all ^ i.x];
        ans /= 2;
    }
    cout << ans;
}