【题目描述】

在某城市里住着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;  	  }