【题解】团伙
【题目描述】
在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足：
1、我朋友的朋友是我的朋友；
2、我敌人的敌人是我的朋友；
所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？
【输入描述】
第1行为n和m，1<n<1000,1<=m<=100 000；
以下m行，每行为p x y，p的值为0或1，p为0时，表示x和y是朋友，p为1时，表示x和y是敌人。
【输出描述】
一个整数，表示这n个人最多可能有几个团伙。
【样例输入】
6 4 1 1 4 0 3 5 0 4 6 1 1 2
【样例输出】
3
【题目分析】
朋友的朋友是朋友（传递性）。
敌人的敌人是朋友（敌人的传递性）。
我们需要根据给定的朋友和敌人关系，将所有可能的朋友合并到同一个集合（团伙）中，最后统计集合的数量。
[解题思路]
并查集数据结构：
使用并查集来维护朋友关系。
每个节点的根节点代表它所属的团伙。
处理朋友关系（p=0）：
直接合并
x和y所在的集合。处理敌人关系（p=1）：
如果
x已经有敌人，那么y应该和x的敌人是朋友。如果
y已经有敌人，那么x应该和y的敌人是朋友。如果
x和y是敌人，那么x的敌人集合和y的敌人集合需要合并。具体来说：
可以用一个数组
enemy来记录每个人的敌人。统计团伙数量：
遍历所有人，统计不同根节点的数量。
【参考答案】
#include<iostream>
using namespace std;
int rank[100],fa[100];
int enemy[100];//enemy[i]表示i的敌人
//初始化
void init(int n)
{
for (int i = 1; i <= n; ++i)
{
fa[i] = i;
rank[i] = 1;
}
}
//查找
int find(int x)
{
if(x == fa[x])
return x;
else{
fa[x] = find(fa[x]); //父节点设为根节点
return fa[x]; //返回父节点
}
}
//合并
void merge(int x,int y) {
x=find(x); //寻找 x的根节点
y=find(y); //寻找 y的根节点
if(x==y) return ; //如果 x和 y的根节点一致，说明他们共属同一集合，则不需要合并，直接返回；否则，执行下面的逻辑
if(rank[x]>rank[y]) //如果 x的高度大于 y，则令 y的上级为 x
fa[y]=x;
else {
if(rank[x]==rank[y]) //如果 x的高度和 y的高度相同，则令 y的高度加1
rank[y]++;
fa[x]=y; //让 x的上级为 y
}
}
int main(){
int n,m;
cin>>n>>m;
init(n);//初始化
for(int i=0;i<m;i++){
int p,x,y;
cin>>p>>x>>y;
if(p==0){
//如果x和y是朋友，直接合并
merge(x,y);
} else{
//x和y是敌人
if(enemy[x]==0){
enemy[x]=y;
} else{
//x的敌人是enemy[x],
//y应该和enemy[x]是朋友
merge(y,enemy[x]);
}
if(enemy[y]==0){
enemy[y]=x;
}else{
//y的敌人是enemy[y]
//x 应该和 enemy[y] 是朋友
merge(x,enemy[y]);
}
}
}
//统计团伙数量（不同根的数量）
int count=0;
for(int i=1;i<=n;i++){
if(find(i)==i){
count++;
}
}
cout<<count;
return 0;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。