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
",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 1005
int 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
",num);
}
int main()
{
//freopen("F:\rush.txt","r",stdin);
input_data();
get_ans();
output_ans();
return 0;
}