洛谷 P1892 [BOI2003]团伙（并查集）

骑猪看日落 2022-01-11 07:13 156阅读 0赞

### **嗯...** ###

## ##

### **题目链接：**[https://www.luogu.org/problemnew/show/P1892][https_www.luogu.org_problemnew_show_P1892] ###

# #

## **通过读题可以很清楚的发现这是一个并查集的题，并且要有两个集合：** ##

### **若他们p和q是朋友，则存入第一个集合；若他们是敌人，则存入第二个集合——即反集（很模糊的一个东西** ###

### **因为最多只有n个数，所以我们将f数组一分为二，f \[1\] ~ f \[n\] 为第一个集合， f \[n+1\] ~ f \[n + n\] 为反集，然后根据题意进行并查集的基本操作即可...** ###

## **本题细节：** ##

### **(1) 注意读题，最后要求的一共有多少个团伙（即我们合并后一共有多少个父亲）， 我们只需要从1 for 到 n，如果f \[i\] == i，ans++即可。** ###

### **(2) 注意我们在f 数组中存了两个集合，会用到2 \* n，所以在初始化f 数组的时候需要从1 for 到 2 \* n。** ###

### **(3) c，p，q的读入只能使用cin， scanf会爆掉。** ###

### **(4) 第一个集合（p和q为朋友）直接合并即可，而反集的合并需要两次合并。（只能这么理解吧...详见代码** ###

### **(5) 注意反集时find函数中的参数，而不是在find函数外再加n。** ###

# #

## **AC代码：** ##

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<iostream>
     3 #include<algorithm>
     4 
     5 using namespace std;
     6 
     7 int f[10005], ans;
     8 int n, m, p, q;
     9 char c;
    10 
    11 inline int find(int x){
    12     if(f[x] != x)
    13         f[x] = find(f[x]);
    14     return f[x];
    15 }
    16 
    17 int main(){
    18     scanf("%d%d", &n, &m);
    19     for(int i = 1; i <= n * 2; i++)//注意两倍 
    20         f[i] = i;
    21     for(int i = 1; i <= m; i++){
    22         cin >> c >> p >> q;
    23         if(c == 'F'){
    24             f[find(p)] = find(q);//是朋友直接合并 
    25         }
    26         if(c == 'E'){
    27             f[find(p + n)] = find(q);//反集合并两次，注意在find函数中的参数 
    28             f[find(q + n)] = find(p);
    29         }
    30     }
    31     for(int i = 1; i <= n; i++){
    32         if(f[i] == i) ans++;//自己为根节点的个数，即集团个数 
    33     }
    34     printf("%d", ans);
    35     return 0;
    36 }

AC代码

转载于:https://www.cnblogs.com/New-ljx/p/10883425.html

[https_www.luogu.org_problemnew_show_P1892]: https://www.luogu.org/problemnew/show/P1892
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220111/ea0c3d47dbe9426eb945759d4e81eae3.png