【9009】团伙

团伙"/>

【9009】团伙

Time Limit: 1 second
Memory Limit: 128 MB

【问题描述】

在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足： 1.我朋友的朋友是我的朋友； 2.我敌人的敌人是我的朋友 所有是朋友的人组成一个团伙。告诉你冠以这n个人的m条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，就计算出这个城市最多可能有多少个团伙？ 

【输入格式】

第1行为n和m，(1< n < 1000),(1<=m<=100000) 以下m行，每行为p x y，p的值为0或1，p为0时，表示x和y是朋友，p为1时，表示x和y是敌人。

【输出格式】

一个整数，表示这n个人最多可能有几个团伙

Sample Input

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

Sample Output

3

【题解】(两类方法)

法一：

给并查集数组多开n个位置。

这时f[x+n]表示x的直系敌人的朋友所在的集合。

这样找可以根据所有人的直系敌人，找到所有人的敌人的敌人，也就是所有人的间接朋友。

在输入 1 x y 时执行这两句

hebing(x+n,y)与hebing(x,y+n);

假如x没有任何直系敌人。

则y就与x+n两个元素构成一个集合。

如果又有z与x是敌人关系,则z,y,x+n构成一个集合。

最后判断团伙的时候不管n以上的东西。只看n一下的f数组即可。即x+n只起到一个串联作用。桥梁。嗯这样解释可以吗。

【代码1】

#include <cstdio>int n,m,f[2010],ans = 0;int findfather(int t) //并查集的找根函数和路径压缩 
{if (f[t] != t)f[t] = findfather(f[t]);return f[t];
}void hebing(int x,int y) //把x元素和y元素合并到同一个集合当中。 
{int r1 = findfather(x),r2 = findfather(y);if (r1!=r2)f[r2] = r1;	
}void input_data()
{scanf("%d%d",&n,&m);for (int i = 1;i <= 2*n;i++) //n以上是i-n的敌人的朋友所在集合的标志元素(桥梁) f[i] = i;for (int i = 1;i <= m;i++){int p,x,y;scanf("%d%d%d",&p,&x,&y);if (p == 0) //如果是朋友就直接合并 hebing(x,y);else //否则,就把各自加入到对方的敌人的朋友的行列中。 {hebing(x,y+n);hebing(x+n,y);	}}		
}void get_ans()
{bool bo[2010];for (int i = 1;i <= n;i++) //要再进行一次路径压缩。保证每个集合的元素都指向根节点。 findfather(i);for (int i = 1;i <= 2*n;i++) //这是用于判断有几个团伙 bo[i] = false;for (int i = 1;i <= n;i++) //根据bo数组来确定有几个团伙。 if (bo[f[i]] == false){bo[f[i]] = true;ans++;}printf("%d\n",ans);
}int main()
{//freopen("F:\\rush.txt","r",stdin);input_data();get_ans();return 0;	
}

法二：

先把敌人的信息以图的形式存储。无向图。

朋友还是直接合并。

最后用for循环来寻找i的两个直系敌人，然后把它们合并在一起。这里f数组只要开到n.思路与上面的程序是相同的。但是更直观一点。

【代码2】

#include <cstdio>
#include <cstring>
#include <cstring>
#define maxren 1005int n,m,pengyou[maxren],enemy[maxren][maxren]; //pengyou相当于f数组,enemy是将敌人关系用图的形式记录下来int findfather(int x) //寻根 + 路径压缩。 
{if (pengyou[x] != x)pengyou[x] = findfather(pengyou[x]);return pengyou[x];	
}void hebing(int x,int y) //把x元素和y元素合并起来 
{int r1 = findfather(x),r2 = findfather(y);	if (r1!=r2)pengyou[r2] = r1;
}void input_data()
{memset(enemy,0,sizeof(enemy));scanf("%d%d",&n,&m);	for (int i = 1;i <= n;i++)pengyou[i] = i;for (int i = 1;i <= m;i++){int p,x,y;scanf("%d%d%d",&p,&x,&y);if (p == 0)hebing(x,y);	else //如果是敌人就建立一条无向边。 {enemy[x][0]++;enemy[x][enemy[x][0]] = y;enemy[y][0]++;enemy[y][enemy[y][0]] = x;}}
}void get_ans()
{for (int i = 1;i <= n;i++) //用3层for循环来找i的直系敌人。找到两个然后他们就是朋友了。 for (int j = 1;j <= enemy[i][0]-1;j++)for (int k = j+1;k <= enemy[i][0];k++){int r1 = findfather(enemy[i][j]);int r2 = findfather(enemy[i][k]);if (r1!=r2)pengyou[r2] = r1;}}void output_ans() //最后用判重的方法找到团伙数 （也可以用排序的方法，相同元素会聚在一起) 
{bool bo[1010];memset(bo,false,sizeof(bo));int num = 0;for (int i = 1;i <= n;i++)findfather(i);for (int i = 1;i <= n;i++)if (!bo[pengyou[i]]){bo[pengyou[i]] = true;num++;	}printf("%d\n",num);}int main()
{//freopen("F:\\rush.txt","r",stdin);input_data();get_ans();output_ans();return 0;	
}