A27700. 团伙(group)
填空题
困难
知识点
题目描述
团伙(group)
题目描述
在某城市里住着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是敌人。
输出
一个整数，表示这n个人最多可能有几个团伙。
输入样例
6 4
1 1 4
0 3 5
0 4 6
1 1 2输出样例
3参考答案
#include<bits/stdc++.h>
using namespace std;
#define N 1005
int n, m, fa[N], enemy[N];//fa[i]：i的双亲 enemy[i]：i的某个敌人
void init(int n)
{
for(int i = 1; i <= n; ++i)
fa[i] = i;
}
int find(int x)//查找x所在集合的根结点
{
if(fa[x] == x)
return x;
return fa[x] = find(fa[x]);
}
void merge(int x, int y)//合并x，y所在的集合
{
fa[find(x)] = find(y);
}
int main()
{
char opt;
int p, q, ct = 0;
cin >> n >> m;
init(n);
for(int i = 1; i <= m; ++i)
{
cin >> opt >> p >> q;
if(opt == 'F')
merge(p, q);
else //opt = 'E' 敌人
{
if(enemy[p])//如果p有敌人enemy[p]
merge(enemy[p], q);//将q加入到p敌人组成的集合
else//如果p没有敌人
enemy[p] = q;//q作为p的敌人
if(enemy[q])
merge(enemy[q], p);
else
enemy[q] = p;
}
}
for(int i = 1; i <= n; ++i)
if(fa[i] == i)//i是根结点
ct++;
cout << ct;
return 0;
}
上一题
下一题