当前位置:网站首页>L2-024 tribe (25 points)
L2-024 tribe (25 points)
2022-04-23 13:57:00 【Heigu Xiaojian】
The question :
In a community , Everyone has their own small circle , It may also belong to many different circles of friends at the same time . We think that friends of friends are all included in a tribe , So I want you to count , In a given community , How many different tribes are there ? And check if any two people belong to the same tribe .
Ideas :
A very naked and check the collection , Note that after connecting the edges, traverse again to make sure that the edges are connected , Then continue the query operation
Code :
#include<bits/stdc++.h>
#include<sstream>
#include<unordered_map>
#define endl '\n'
using namespace std;
const int maxn=10005;
int p[maxn],a[maxn];
int findx(int x)
{
if(p[x]!=x)
{
return p[x]=findx(p[x]);
}
else {
return p[x];
}
}
unordered_map<int ,int >mo;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,i,j,k,t,cnt=0,cnt1=0,q;
cin>>n;
for(i=1;i<maxn;i++) p[i]=i;
for(i=0;i<n;i++)
{
cin>>k;
int t=-1,d;
for(j=0;j<k;j++)
{
cin>>d;
if(mo[d]==0){
mo[d]++;
cnt++;
}
if(t==-1) {
t=d;
}
else {
int m1=findx(t);
int m2=findx(d);
if(m1!=m2)
{
p[m2]=m1;
}
}
}
}
mo.clear();
for(i=1;i<=cnt;i++)
{
p[i]=findx(p[i]);
if(mo[p[i]]==0) cnt1++;
mo[p[i]]++;
}
cin>>q;
cout<<cnt<<" "<<cnt1<<endl;
for(i=0;i<q;i++)
{
int u,v;
cin>>u>>v;
if(findx(u)!=findx(v))
{
cout<<"N"<<endl;
}
else {
cout<<"Y"<<endl;
}
}
return 0;
}
版权声明
本文为[Heigu Xiaojian]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204231347361092.html
边栏推荐
- 淘宝发布宝贝提示“您的消保保证金额度不足,已启动到期保障”
- Atcoder beginer contest 248c dice sum (generating function)
- YARN线上动态资源调优
- Choreographer全解析
- Core concepts of microservice architecture
- sys. dbms_ scheduler. create_ Job creates scheduled tasks (more powerful and rich functions)
- JS brain burning interview question reward
- Jiannanchun understood the word game
- Leetcode? The first common node of two linked lists
- Reading notes: fedgnn: Federated graph neural network for privacy preserving recommendation
猜你喜欢
elmo(BiLSTM-CRF+elmo)(Conll-2003 命名实体识别NER)
MySQL [read / write lock + table lock + row lock + mvcc]
记录一个奇怪的bug:缓存组件跳转之后出现组件复制
try --finally
Strange bug of cnpm
神经元与神经网络
Express ② (routing)
freeCodeCamp----time_ Calculator exercise
淘宝发布宝贝提示“您的消保保证金额度不足,已启动到期保障”
Dolphin scheduler source package Src tar. GZ decompression problem
随机推荐
SSM project deployed in Alibaba cloud
Window analysis function last_ VALUE,FIRST_ VALUE,lag,lead
Detailed explanation of Oracle tablespace table partition and query method of Oracle table partition
freeCodeCamp----arithmetic_ Arranger exercise
The art of automation
解决方案架构师的小锦囊 - 架构图的 5 种类型
Question bank and answer analysis of the 2022 simulated examination of the latest eight members of Jiangxi construction (quality control)
Generate 32-bit UUID in Oracle
[code analysis (7)] communication efficient learning of deep networks from decentralized data
[code analysis (2)] communication efficient learning of deep networks from decentralized data
leetcode--380.O(1) 时间插入、删除和获取随机元素
Analysis of cluster component gpnp failed to start successfully in RAC environment
cnpm的诡异bug
Small case of web login (including verification code login)
10g database cannot be started when using large memory host
第十五章 软件工程新技术
China creates vast research infrastructure to support ambitious climate goals
Parameter comparison of several e-book readers
AtomicIntegerArray源码分析与感悟
Basic SQL query and learning