백준19028 Link Cut Digraph

작성일 | In

문제 링크

  • http://icpc.me/19028

사용 알고리즘

  • Offline Incremental SCC

시간복잡도

  • $O(M \log M)$

풀이

BOJ 8496 Godzilla(2009 POI ONTAK) 문제 풀이에서 설명한 Offline Incremental SCC를 구현하는 문제입니다.

해당 알고리즘에서 UnionFind가 관리하는 정보를 잘 이해하고 있다면 쉽게 문제를 풀 수 있습니다.

전체 코드

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#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;
using PII = pair<int, int>;

template<size_t _Sz> struct UnionFind {
    int P[_Sz], S[_Sz]; ll CS;
    UnionFind(){ iota(P, P+_Sz, 0); fill(S, S+_Sz, 1); CS = 0; }
    int find(int v){ return v == P[v] ? v : P[v] = find(P[v]); }
    bool merge(int u, int v){
        u = find(u); v = find(v);
        if(u == v) return false;
        CS -= 1LL * S[u] * (S[u] - 1) / 2;
        CS -= 1LL * S[v] * (S[v] - 1) / 2;
        S[v] += S[u];
        CS += 1LL * S[v] * (S[v] - 1) / 2;
        P[u] = v; return true;
    }
};

template<size_t _Sz> struct SCC {
    vector<int> G[_Sz], R[_Sz], dfn, use;
    int id[_Sz], pv;
    int cnt[_Sz];
    void clear(){
        for(auto i : use) cnt[id[i]] = 0, G[i].clear(), R[i].clear(), id[i] = 0;
        dfn.clear(); use.clear(); pv = 0;
    }
    void addEdge(int s, int e){
        G[s].push_back(e);
        R[e].push_back(s);
        use.push_back(s);
        use.push_back(e);
    }
    void dfs(int v){
        id[v] = 1;
        for(auto i : G[v])  if(id[i]) dfs(i);
        dfn.push_back(v);
    }
    void rfs(int v, int color){
        id[v] = color; cnt[color]++;
        for(auto i : R[v])  if(id[i]) rfs(i, color);
    }
    void getSCC(){
        for(auto i : use) if(!id[i]) dfs(i);
        reverse(all(dfn));
        for(auto i : use) id[i] = 0;
        for(auto i : dfn) if(!id[i]) rfs(i, ++pv);
    }
};

int N, M;
PII E[252525];
UnionFind<101010> uf;
SCC<101010> scc;
int Time[252525];
ll Res[252525];

void Solve(int s, int e, const vector<int> &li){
    if(s == e){
        for(const auto &i : li) uf.merge(E[i].x, E[i].y), Time[i] = s;
        Res[s] = uf.CS;
        return;
    }
    scc.clear();

    int m = s + e >> 1;
    for(const auto &i : li){
        int st = uf.find(E[i].x), ed = uf.find(E[i].y);
        if(i <= m) scc.addEdge(st, ed);
    }
    scc.getSCC();

    vector<int> l, r;
    for(const auto &i : li){
        if(i > m){ r.push_back(i); continue; }
        int st = uf.find(E[i].x), ed = uf.find(E[i].y);
        if(scc.id[st] == scc.id[ed]) l.push_back(i);
        else r.push_back(i);
    }
    Solve(s, m, l);
    Solve(m+1, e, r);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(int i=1; i<=M; i++) cin >> E[i].x >> E[i].y;

    vector<int> li;
    li.resize(M);
    iota(all(li), 1);
    Solve(1, M+1, li);

    for(int i=1; i<=M; i++) cout << Res[i] << "\n";
}