洛谷1197并查集拆集合

链接：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
", s.top());
107             s.pop();
108         }
109     }
110 
111     return 0;
112 }