UVALive 6910 Cutting Tree（离线逆序并查集）

【题目】：（地址：）

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=97671#problem/E

【题意】：

给出多棵树和两类操作：操作（C x）删除结点 x 与其父结点的连边；操作（Q a b）询问 a b 是否连通。

【解题思路】：

连通性的查询容易想到用并查集，关键在于如何处理删边。

考虑到删边的难点在于查询时的路径压缩导致某些结点与其父结点"不直接相连"，这里使用离线处理，在查询之前把所有该删的边删除，同时逆序处理询问操作；当逆序处理到删边操作时，复原删掉的边（删除变为增边）。

【代码】：（上了个比较标准的并查集模板）

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<stack>
  6 #include<algorithm>
  7 #define LL long long
  8 #define maxn 25000
  9 #define IN freopen("in.txt","r",stdin);
 10 using namespace std;
 11 
 12 
 13 struct Union_Find_Set{
 14 
 15     int fa[maxn];    /*每个结点的父亲节点编号*/
 16     int rank[maxn];    /*树的高度*/
 17 
 18     /*构造并查集并初始化*/
 19     void make_set()
 20     {
 21         for(int i=0; i<maxn; i++){
 22             fa[i] = i;    /*初始时本身构成一个集合，根为本身*/
 23             rank[i] = 0;
 24         }
 25     }
 26 
 27     /*递归查找结点所在树的根节点*/
 28     int find_set(int x)
 29     {
 30         /*路径压缩*/
 31         return x!=fa[x]? fa[x]=find_set(fa[x]) : x;
 32     }
 33 
 34     /*合并两个集合*/
 35     void unite_set(int x, int y)
 36     {
 37         x = find_set(x);
 38         y = find_set(y);
 39         /*记录树的高度防止合并后退化，rank小的向rank大的连接*/
 40         if(rank[x] < rank[y]) swap(x,y);
 41         fa[y] = x;    /*合并*/
 42         if(rank[x] == rank[y]) rank[x]++;    /*高度相同则加1*/
 43     }
 44 
 45     /*判断两结点是否属于同一集合*/
 46     bool same_set(int x, int y)
 47     {
 48         return find_set(x) == find_set(y);
 49     }
 50 }UFS;
 51 
 52 int n,q;
 53 struct node{
 54     char type;
 55     int first, second;
 56 };
 57 
 58 stack<node> s;
 59 stack<bool> ans;
 60 
 61 int main(int argc, char const *argv[])
 62 {
 63     //IN;
 64 
 65     int t,ca=1;scanf("%d",&t);
 66     while(t--)
 67     {
 68         scanf("%d %d",&n,&q);
 69 
 70         while(!s.empty()) s.pop();
 71         while(!ans.empty()) ans.pop();
 72         UFS.make_set();
 73 
 74         for(int i=1; i<=n; i++){
 75             scanf("%d",&UFS.fa[i]);
 76             if(!UFS.fa[i]) UFS.fa[i] = i;
 77         }
 78 
 79         for(int i=1; i<=q; i++)
 80         {
 81             node tmp_node;
 82             getchar();
 83             scanf("%c",&tmp_node.type);
 84             if(tmp_node.type=='Q'){
 85                 scanf("%d %d",&tmp_node.first, &tmp_node.second);
 86             }
 87             else{
 88                 scanf("%d",&tmp_node.first);
 89                 tmp_node.second = UFS.fa[tmp_node.first];
 90                 /*离线处理--询问之前删边,避免路径压缩导致删边失效*/
 91                 UFS.fa[tmp_node.first] = tmp_node.first;
 92             }
 93             s.push(tmp_node);
 94         }
 95 
 96         while(q--)
 97         {
 98             node tmp_node = s.top(); s.pop();
 99 
100             if(tmp_node.type=='Q'){
101                 if(UFS.same_set(tmp_node.first, tmp_node.second)) ans.push(1);
102                 else ans.push(0);
103             }
104             else{
105                 UFS.fa[tmp_node.first] = tmp_node.second;
106             }
107         }
108 
109         printf("Case #%d:
", ca++);
110         while(!ans.empty())
111         {
112             if(ans.top() == 1) puts("YES");
113             else puts("NO");
114             ans.pop();
115         }
116     }
117 
118     return 0;
119 }