并查集--团伙-朋友问题.doc

并查集-朋友问题 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 #includeiostream 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 (nm) root[m]=n; else root[n]=m; return 0; } int main() { int n,m; int i,j,k; char c; int x,y; cinnm; for(i=1;i=1001;i++) root[i]=-1; for (i=1;i=m;i++) { cincxy; 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;ji;j++) //通过以当前位置的前一位置向下辐射，即每次查找一个方阵 { if(relate[i][j]) { for (k=1;ki;k++)//小于i是为了防止二次合并，即构成方阵 { if (relate[j][k]) hb(k,i); } } } } int s=0; for(i=1;i=n;i++) { if(root[i]==-1) s++; } coutsendl; return 0; } /*首先，如果两人是朋友，那么就把两人合并。 除此之外，我们再维护一个e[i]，表示i的一个敌人。如果两人是敌人，那么如果e[i]为空，就更新e[i]，否则，就把e[i]和j合并。根据敌人的敌人是朋友的原则，如果j和i是敌人，那么j同e[i]则是朋友，所以合并。同样的，对于i和e[j]，也是如此。最后统计一下根结点就行了。 #includecstdio #includecstdlib #includecstring #includeiostream using namespace std; int n,m; const int maxn=1000; int f[maxn+10],e[maxn+10]; int find(int x) { if (f[x]==x) return f[x]; f[x]=find(f[x]); return f[x]; } void together(int a,int b) { int aa=find(a),bb=find(b); f[aa]=f[bb]; } int main() { scanf(%d%d,n,m); for (int i=1; i=n; i++) f[i]=i; while(m--) { char flag=(getchar(),getchar()); int a,b; scanf(%d%d,a,b); if(flag==F) together(a,b); else { if(!e[a]) e[a]=b; else together(e[a],b); if(!e[b]) e[b]=a; else together(e[b],a); } } int ans=0; for(int i=1