Junk-Mail Filter 【并查集虚父节点】

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2473

题目大意：

n个点,m个操作,操作时,输入M a b，表示a,b在一个集合里,输入S a 表示将a从集合里删除掉。求最后有多少个不同的集合。

解题思路:

需要删除结点，但是并非是删除与该节点为父亲节点的子树，而仅仅是该点。所以需要用到虚父节点。

所以再开一个数组，更新节点时直接改变当前节点的父节点，使其等于大于n的父节点，这样就把其节点删除了。

代码如下：

 1 #include<iostream>
 2 #include<string.h>
 3 #define mem(a,b) memset(a,b,sizeof(a))
 4 using namespace std;
 5 const int MAXN = 1e6 + 100;
 6 
 7 int n,m,temp,k;
 8 char op;
 9 int p[MAXN],pre[MAXN],flag[MAXN];
10 
11 int find(int x)
12 {
13     if(pre[x] == x)
14         return x;
15     else
16     {
17         int root = find(pre[x]);
18         pre[x] = root;
19         return pre[x];
20     }
21 }
22 
23 int main()
24 {
25     cin.sync_with_stdio(false);
26     k = 1;
27     while(cin >> n >> m)
28     {
29         if(n == 0 && m == 0)
30             break;
31         temp = n,mem(flag,0);
32         for(int i = 0; i < n; i ++)
33         {
34             pre[i] = i;
35             p[i] = i;  //虚设 
36         }
37         for(int i = 1; i <= m;  i++)
38         {
39             cin >> op;
40             if(op == ‘M‘)
41             {
42                 int a,b;
43                 cin >> a >> b;
44                 int x = find(p[a]),y = find(p[b]);
45                 if(x != y)
46                     pre[y] = x;
47             }
48             else
49             {
50                 int a;
51                 cin >> a;
52                 p[a] = temp;
53                 pre[temp] = temp;
54                 temp ++;
55             }
56         }
57         int ans = 0;
58         for(int i = 0; i < n; i ++)
59         {
60             int x = find(p[i]);
61             if(!flag[x])
62             {
63                 ans ++;
64                 flag[x] = 1;
65             }
66         }
67         cout << "Case #" << k ++ << ": " << ans << endl;
68     }
69     return 0;
70 }

?

同样有一道一样题，更加直观。

乱世天下，诸侯割据。每个诸侯王都有一片自己的领土。但是不是所有的诸侯王都是安分守己的，实力强大的诸侯国会设法吞并那些实力弱的，让自己的领土 面积不断扩大。而实力弱的诸侯王为了不让自己的领土被吞并，他会联合一些其他同样弱小的诸侯国，组成联盟(联盟不止一个)，来共同抵抗那些强大的诸侯国。 强大的诸侯国为了瓦解这些联盟，派出了最优秀的间谍来离间他们，使一些诸侯国退出联盟。最开始，每个诸侯国是一个联盟。

有两种操作

1、U x y 表示x和y在同一个联盟。（0≤x，y<n）

2、D x?? 表示x退出联盟。 仅仅是x退出联盟，对于其他的诸侯国没有影响。因此是删除单个点而不是子树。

输入

多组测试数据
第一行两个数，n和m（1 ≤ n≤ 10^5,1 ≤ m ≤10^5），分别表示诸侯国的个数和操作次数。
接下来有m行操作

输出

输出联盟的个数

样例输入

5 7

U 0 1

U 1 2

U 0 3

D 0

U 1 4

D 2

U 0 2

10 1

U 0 9?

样例输出

Case #1: 2

Case #2: 9

 1 #include<iostream>
 2 #include<string.h>
 3 #define mem(a,sizeof(a))
 4 using namespace std;
 5 const int MAXN = 1e5 + 10;
 6 
 7 int n,k;
 8 char op;
 9 int p[MAXN],pre[10 * MAXN],flag[10 * MAXN];
10 
11 int find(int x)
12 {
13     if(pre[x] == x)
14         return x;
15     else
16     {
17         int root = find(pre[x]);
18         pre[x] = root;
19         return pre[x];
20     }
21 }
22 
23 int main()
24 {
25     cin.sync_with_stdio(false);
26     k = 1;
27     while(cin >> n >> m)
28     {
29         temp = n,0);
30         for(int i = 0; i < n; i ++)
31         {
32             pre[i] = i;
33             p[i] = i;  //虚设 
34         }
35         for(int i = 1; i <= m;  i++)
36         {
37             cin >> op;
38             if(op == ‘U‘)
39             {
40                 int a,b;
41                 cin >> a >> b;
42                 int x = find(p[a]),y = find(p[b]);
43                 if(x != y)
44                     pre[y] = x;
45             }
46             else
47             {
48                 int a;
49                 cin >> a;
50                 p[a] = temp;
51                 pre[temp] = temp;
52                 temp ++;
53             }
54         }
55         int ans = 0;
56         for(int i = 0; i < n; i ++)
57         {
58             int x = find(p[i]);
59             if(!flag[x])
60             {
61                 ans ++;
62                 flag[x] = 1;
63             }
64         }
65         cout << "Case #" << k ++ << ": " << ans << endl;
66     }
67     return 0;
68 }

View Code