当前位置:网站首页>L2-024 部落 (25 分)(并查集)
L2-024 部落 (25 分)(并查集)
2022-04-23 08:43:00 【.Ashy.】
描述:
在一个社区里,每个人都有自己的小圈子,还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里,于是要请你统计一下,在一个给定社区中,到底有多少个互不相交的部落?并且检查任意两个人是否属于同一个部落。
输入格式:
输出:
首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询,如果他们属于同一个部落,则在一行中输出Y,否则输出N。
输入样例:
4
3 10 1 2
2 3 4
4 1 5 7 8
3 9 6 4
2
10 5
3 7
输出样例:
10 2
Y
N
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const ll maxx = 1e18;
const int N = 1e6+100;
const int p = 1e4+10;
const double eps = 1e-8;
int n,m,t,k;
int a,bs;
int b[p];
int pre[N],max1,cnt;
map<int,int>mp;
int find(int x)
{
if(x==pre[x]) return x;
else return pre[x]=find(pre[x]);
}
void unionn(int x,int y)
{
int ya=find(x);
int yb=find(y);
pre[ya]=yb;
}
int main()
{
cin>>n;
for(int i=1;i<=1e6;i++)
{
pre[i]=i;
}//处理根节点
for(int i=1;i<=n;i++)
{
cin>>k;
for(int j=1;j<=k;j++)
{
cin>>b[j];
max1=max(max1,b[j]);
}//输入,找出总人数
for(int j=1;j<=k;j++)
{
for(int s=j+1;s<=k;s++)
{
unionn(b[j],b[s]);
}
}//并
}
cin>>m;
for(int i=1;i<=max1;i++)
{
if(mp[find(i)]==0)
{
mp[find(i)]=1;
cnt++;
}//找不相交集合个数
}
cout<<max1<<" "<<cnt<<endl;
for(int i=1;i<=m;i++)
{
cin>>a>>bs;
if(find(a)==find(bs))
cout<<"Y"<<endl;
else
cout<<"N"<<endl;
}//查
return 0;
}
版权声明
本文为[.Ashy.]所创,转载请带上原文链接,感谢
https://blog.csdn.net/woshilichunyang/article/details/124357487
边栏推荐
猜你喜欢
GUI编程简介 swing
On time atom joins hands with oneos live broadcast, and the oneos system tutorial is fully launched
1099 establish binary search tree (30 points)
经典题目刷一刷
Reference passing 1
Failed to convert a NumPy array to a Tensor(Unsupported Object type int)
Overview of bus structure
STM32 uses Hal library. The overall structure and function principle are introduced
Get the absolute path of the class according to the bytecode
测试你的机器学习流水线
随机推荐
DJ音乐管理软件Pioneer DJ rekordbox
OneFlow學習筆記:從Functor到OpExprInterpreter
How to generate assembly file
Whether the same binary search tree (25 points)
应纳税所得额
Idea is configured to connect to the remote database mysql, or Navicat fails to connect to the remote database (solved)
关于cin,scanf和getline,getchar,cin.getline的混合使用
Go语言自学系列 | golang嵌套结构体
深度学习框架中的自动微分及高阶导数
Reference passing 1
php基于哈希算法出现的强弱比较漏洞
cadence的工艺角仿真、蒙特卡洛仿真、PSRR
Redis master-slave server problem
匿名類型(C# 指南 基礎知識)
Excle plus watermark
Illegal character in scheme name at index 0:
HAL库的RCC简介
Input / output system
洋桃电子STM32物联网入门30步笔记二、CubeIDE下载、安装、汉化、设置
搜索树判断 (25 分)