【题目描述】

在某城市里住着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是敌人。

【输出描述】

【样例输入】

6 4
1 1 4
0 3 5
0 4 6
1 1 2

【样例输出】

3

【题目分析】

1. 朋友的朋友是朋友（传递性）。

2. 敌人的敌人是朋友（敌人的传递性）。

我们需要根据给定的朋友和敌人关系，将所有可能的朋友合并到同一个集合（团伙）中，最后统计集合的数量。

[解题思路]

1. 并查集数据结构：

• 使用并查集来维护朋友关系。

• 每个节点的根节点代表它所属的团伙。

2. 处理朋友关系（p=0）：

• 直接合并 x 和 y 所在的集合。

3. 处理敌人关系（p=1）：

• 如果 x 已经有敌人，那么 y 应该和 x 的敌人是朋友。

• 如果 y 已经有敌人，那么 x 应该和 y 的敌人是朋友。

• 如果 x 和 y 是敌人，那么 x 的敌人集合和 y 的敌人集合需要合并。

• 具体来说：

• 可以用一个数组 enemy 来记录每个人的敌人。

4. 统计团伙数量：

• 遍历所有人，统计不同根节点的数量。

【参考答案】

#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;
	
}