alan23273850 的刷題筆記
d449: 垃圾信件
Tags: disjoint-set
出處：https://zerojudge.tw/ShowProblem?problemid=d449
提交：https://zerojudge.tw/Submissions?problemid=d449&account=allllllan123456
問題：給你信件數量 $n\in[1,10000]$ (編號 1 到 $n$) 以及 $m\in[1,1000000]$ 筆操作，操作 $1$ $x$ $y$ 代表將第 $x$ 和 $y$ 封信分成同類 (與 $x$ 或 $y$ 同類的其他信件也會變成同類)，操作 $2$ $x$ 代表將第 $x$ 封信獨立出來自成一類。假設一開始每封信都是自成一類，請問最後這些信總共會被分成幾類。
解法：典型並查集，但這題不一樣的是還多了所謂的「獨立操作 (isolate)」，我參考 morris 大的虛設點技巧，賦予被獨立的信件一個新的號碼，而其原有的號碼則留在樹中維持既有的結構。合併操作有效時 (原本的兩信件屬不同一類) 總分類數減一，獨立操作有效時 (原本的信件有同伴) 總分類數加一。
附註：
[1] https://mypaper.pchome.com.tw/zerojudge/post/1322413367
1#include <bits/stdc++.h>
2using namespace std;
3
4int size[1000001], p[1000001], reaL[1000001];
5
6inline int find(int x) {
7 return x == p[x] ? x : p[x] = find(p[x]);
8}
9
10int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
11 int n, m, op, group;
12 while (cin >> n >> m) { group = n;
13 for (int i=1; i<=n; i++)
14 p[i] = reaL[i] = i, size[i] = 1;
15 while (m--) { int x, oldx;
16 cin >> op >> x; oldx = x; x = reaL[x];
17 if (op == 1) {
18 int y; cin >> y; y = reaL[y];
19 x = find(x), y = find(y);
20 if (x != y)
21 group--, p[x] = y, size[y] += size[x];
22 } else if (size[find(x)] > 1)
23 group++, size[p[x]]--, reaL[oldx]=++n, p[n]=n, size[n]=1;
24 }
25 cout << group << '\n';
26 }
27 return 0;
28}