链接：https://www.luogu.org/problemnew/show/P1197
题意：一张图，拆开若干次点，问每次拆开后连通分量的个数。
思路：刚开始想着并查集这么拆集合，后来发现拆集合不好拆，【正难则反】，我们可以反过来思考，拆点变成加点。
开始把不在破坏序列的点的边连上。处理集合数量。
然后再安装拆点的逆顺序加点，用并查集维护加点的影响
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 const int maxn = 1e6 + 7; 5 const int maxm = 1e6 + 7; 6 7 int n, m, first[maxn], sign, pre[maxn]; 8 9 int hit[maxn]; 10 bool broke[maxn]; 11 12 struct Edge { 13 int to, w, next; 14 } edge[maxm]; 15 16 void init() { 17 for(int i = 0; i < n; i ++ ) { 18 first[i] = -1; 19 } 20 sign = 0; 21 } 22 23 void add_edge(int u, int v, int w) { 24 edge[sign].to = v; 25 edge[sign].w = w; 26 edge[sign].next = first[u]; 27 first[u] = sign ++; 28 } 29 30 void init_disjoint_set() { 31 for(int i = 0; i < n; i ++ ) { 32 pre[i] = i; 33 } 34 } 35 36 int findx(int x) { 37 return pre[x] == x ? x : pre[x] = findx(pre[x]); 38 } 39 40 void join(int x, int y) { 41 int fx = findx(x), fy = findx(y); 42 if(fx != fy) { 43 pre[fx] = fy; 44 } 45 } 46 47 bool same(int x, int y) { 48 return findx(x) == findx(y); 49 } 50 51 int main() 52 { 53 while(~scanf("%d %d", &n, &m)) { 54 init(); 55 init_disjoint_set(); 56 for(int i = 1; i <= m; i ++ ) { 57 int u, v; 58 scanf("%d %d", &u, &v); 59 add_edge(u, v, 1); 60 add_edge(v, u, 1); 61 } 62 int num; 63 memset(hit, 0, sizeof(hit)); 64 memset(broke, 0, sizeof(broke)); 65 scanf("%d", &num); 66 for(int i = 1; i <= num; i ++ ) { 67 scanf("%d", &hit[i]); 68 broke[ hit[i] ] = 1; 69 } 70 int tot = n - num; 71 for(int i = 0; i < n; i ++ ) { 72 if(broke[i]) { 73 continue; 74 } 75 for(int j = first[i]; ~j; j = edge[j].next) { 76 int to = edge[j].to; 77 if(broke[to]) { 78 continue; 79 } 80 if(!same(to, i)) { 81 join(to, i); 82 tot --; 83 } 84 } 85 } 86 stack<int>s; 87 s.push(tot); 88 for(int i = num; i >= 1; i -- ) { 89 int x = hit[i]; 90 int cnt = 0; 91 for(int j = first[x]; ~j; j = edge[j].next) { 92 int to = edge[j].to; 93 if(broke[to]) { 94 continue; 95 } 96 if(!same(x, to)) { 97 join(x, to); 98 cnt ++; 99 } 100 } 101 tot = tot - (cnt - 1); 102 broke[x] = 0; 103 s.push(tot); 104 } 105 while(!s.empty()) { 106 printf("%d\n", s.top()); 107 s.pop(); 108 } 109 } 110 111 return 0; 112 }