当前位置:网站首页>1385:团伙(group)
1385:团伙(group)
2022-07-08 00:57:00 【一位13岁的编程爱好者】
题目
1385:团伙(group)
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
在某城市里住着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
题目分析:第一条规定很容易实现,使用基本的并查集操作即可;第二条规定可以把每个人所有的敌人使用集合存储起来,操作和第一条就一样了。
具体方法是,为每个人建立一个结构体,包含两个成员,一个是自己的直接首领的编号(dboss),一个是自己所有的敌人(enemies)。然后建立一个函数boss查找一个人所属团伙的最高首领。所有boss相同的人组成一个团伙。这样,当两个人是朋友时,就合并两个人所在的团伙,即将其中一个人的boss的dboss设为另一个人(的boss);当两个人是敌人时,两个人分别与对方的敌人执行上述操作。最后,boss的数目就是所求数目。
C++代码
#include<iostream>
#include<unordered_set>
using namespace std;
struct person
{
short dboss;//该人的直接首领
unordered_set<short> enemies;//该人的敌人
}ps[1005];
short boss(short a)//查找一个人所属团伙的最高首领
{
if (ps[a].dboss != a)
return boss(ps[a].dboss);
return a;
}
void group_merge(short x, short y)//把x和y两个团伙合并
{
ps[boss(x)].dboss = boss(y);
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i)//初始化
ps[i].dboss = i;
while (m--)
{
bool p;
short x, y;
cin >> p >> x >> y;
if (p)//我敌人的敌人是我的朋友
{
for (short i : ps[y].enemies)
{
if (i != x)
group_merge(x, i);
}
for (short i : ps[x].enemies)
{
if (i != y)
group_merge(y, i);
}
ps[x].enemies.insert(y);
ps[y].enemies.insert(x);
}
else//我朋友的朋友是我的朋友
group_merge(x, y);
}
short result = 0;
//直接查不相同的最高首领有多少个
bool b[1005]{
};
for (short i = 1; i <= n; i++)
{
const short bs = boss(i);
if (!b[bs])
{
++result;
b[bs] = true;
}
}
cout << result;
return 0;
}
运行结果
边栏推荐
- 很多小伙伴不太了解ORM框架的底层原理,这不,冰河带你10分钟手撸一个极简版ORM框架(赶快收藏吧)
- excel函数统计已存在数据的数量
- Force buckle 5_ 876. Intermediate node of linked list
- 数据链路层及网络层协议要点
- CV2 read video - and save image or video
- From starfish OS' continued deflationary consumption of SFO, the value of SFO in the long run
- 力扣6_1342. 将数字变成 0 的操作次数
- leetcode 865. Smallest Subtree with all the Deepest Nodes | 865.具有所有最深节点的最小子树(树的BFS,parent反向索引map)
- VR/AR 的产业发展与技术实现
- Little knowledge about TXE and TC flag bits
猜你喜欢
burpsuite
Random walk reasoning and learning in large-scale knowledge base
Nanny level tutorial: Azkaban executes jar package (with test samples and results)
Exit of processes and threads
很多小夥伴不太了解ORM框架的底層原理,這不,冰河帶你10分鐘手擼一個極簡版ORM框架(趕快收藏吧)
Leetcode featured 200 -- linked list
谈谈 SAP iRPA Studio 创建的本地项目的云端部署问题
Coreldraw2022 download and install computer system requirements technical specifications
喜欢测特曼的阿洛
Semantic segmentation | learning record (2) transpose convolution
随机推荐
nmap工具介绍及常用命令
Principle of least square method and matlab code implementation
leetcode 865. Smallest Subtree with all the Deepest Nodes | 865. The smallest subtree with all the deepest nodes (BFs of the tree, parent reverse index map)
Introduction to QT: video player
JVM memory and garbage collection-3-runtime data area / method area
线程死锁——死锁产生的条件
nmap工具介紹及常用命令
Wechat applet uniapp page cannot jump: "navigateto:fail can not navigateto a tabbar page“
CV2 read video - and save image or video
【每日一题】648. 单词替换
[recommendation system paper reading] recommendation simulation user feedback based on Reinforcement Learning
云原生应用开发之 gRPC 入门
adb工具介绍
阿南的判断
Deep understanding of softmax
burpsuite
Vim 字符串替换
Kwai applet guaranteed payment PHP source code packaging
The way fish and shrimp go
Introduction to grpc for cloud native application development