백준6991 계통 트리

작성일 | In

문제 링크

  • http://icpc.me/6991

문제 출처

  • 2008 KOI 고등부 3번

사용 알고리즘

  • 정렬
  • 해싱

시간복잡도

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

풀이

$K = 3$인 계통 그래프에서 (자기 자신을 포함해서) 인접한 정점이 같은 정점끼리 묶어줍시다. 함께 묶인 정점들은 계통 트리 상에서 거리가 2 이하이고, 이 정점들은 계통 트리 상에서 부모 정점이 동일합니다.
묶인 그래프에서 인접한 묶음에 속한 정점들은 계통 트리 상에서 거리가 3입니다. 인접한 묶음의 부모 정점끼리 간선으로 이어주면 계통 트리를 복원할 수 있습니다.

인접한 정점 리스트가 같은지 비교하는 것은, 인접한 정점들을 정렬한 뒤, 리스트를 해싱해서 비교하면 됩니다.

전체 코드

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++17 -DLOCAL
******************************/

#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())
#define IDX(v, x) lower_bound(all(v), x) - v.begin()
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;

constexpr ll P1 = 131071, M1 = 998244353;
constexpr ll P2 = 524287, M2 = 993244853;

int N, M, Ord[5050];
vector<int> G[5050];
ll A[5050], B[5050];

int P[5050], pv;

int R[10101];
int Find(int v){ return v == R[v] ? v : R[v] = Find(R[v]); }
bool Merge(int u, int v){
    u = Find(u); v = Find(v);
    if(u == v) return false;
    R[u] = v; return true;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M; pv = N; iota(R, R+10101, 0);
    for(int i=1; i<=M; i++){
        int s, e; cin >> s >> e;
        G[s].push_back(e);
        G[e].push_back(s);
    }
    for(int i=1; i<=N; i++){
        G[i].push_back(i);
        sort(all(G[i]));
        Ord[i] = i;
    }
    for(int i=1; i<=N; i++){
        for(const auto &j : G[i]){
            A[i] = (A[i] * P1 + j) % M1;
            B[i] = (B[i] * P2 + j) % M2;
        }
    }
    sort(Ord+1, Ord+N+1, [](int a, int b){ return tie(A[a], B[a]) < tie(A[b], B[b]); });

    for(int i=1; i<=N; i++){
        auto t1 = make_pair(A[Ord[i-1]], B[Ord[i-1]]);
        auto t2 = make_pair(A[Ord[i]], B[Ord[i]]);
        if(t1 != t2) pv++;
        P[Ord[i]] = pv;
    }

    cout << pv-1 << "\n";
    for(int i=1; i<=N; i++){
        cout << i << " " << P[i] << "\n";
        for(const auto &j : G[i]) if(Merge(P[i], P[j])) cout << P[i] << " " << P[j] << "\n";
    }
}