文档介绍：并查集-朋友问题
2012-12-10 23:15 18人阅读评论(0) 收藏举报
例一:
整个组织有n个人,任何两个认识的人不是朋友就是敌人,而且满足:①我朋友的朋友是我的朋友;②我敌人的敌人是我的朋友。所有是朋友的人组成一个团伙。现在,警方委派你协助调查,拥有关于这n个人的m条信息(即某两个人是朋友,或某两个人是敌人),请你计算出这个城市最多可能有多少个团伙。
数据范围:2≤N≤1000,1≤M≤1000。
输入数据:第一行包含一个整数N,第二行包含一个整数M,接下来M行描述M条信息,内容为以下两者之一:“F x y”表示x与y是朋友;“E x y”表示x与y是敌人(1≤x≤y≤N)。
输出数据:包含一个整数,即可能的最大团伙数。
样例:
输入:6
4
E 1 4
F 3 5
F 4 6
E 1 2
输出:3
#include<iostream>
using namespace std;
int root[1001]={0};
int relate[1001][1001]={0};
int father(int n)
{
if(root[n]==-1)
return n;
else
return father(root[n]);
}
int hb(int x,int y)
{
int n,m;
n=father(x);
m=father(y);
if (n<m)
root[m]=n;
else
root[n]=m;
return 0;
}
int main()
{
int n,m;
int i,j,k;
char c;
int x,y;
cin>>n>>m;
for(i=1;i<=1001;i++)
root[i]=-1;
for (i=1;i<=m;i++)
{
cin>>c>>x>>y;
if(c=='E')
{
relate[y][x]=1;//记录相互的关系
relate[x][y]=1;
}
if(c=='F')
hb(x,y);
}
for(i=1;i<=n;i++)
{ //遍历关系,合并我的敌人的敌人即朋友
for(j=1;j<i;j++) //通过以当前位置的前一位置向下辐射,即每次查找一个方阵
{
if(relate[i][j])
{
for (k=1;k<i;k++)//小于i是为了防止二次合并,即构成方阵
{
if (relate[j][k])
hb(k,i);
}
}
}
}
int s=0;
for(i=1;i<=n;i++)
{
if(root[i]==-1)
s++;
}
cout<<s<<endl;
return 0;
}
/*首先,如果两人是朋友,那么就把两人合并。
除此之外,我们再维护一个e[i],表示i的一个敌人。如果两人是敌人,那么如果e[i]为空,就更新e[i],否则,就把e[i]和j合并。根据敌人的敌人是朋友的原则,如果j和i是敌人,那么j同e[i]则是朋友,所以合并。同样的,对于i和e[j],也是如此。最后统计