当前位置:网站首页>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
边栏推荐
- Crontab timing task output generates a large number of mail and runs out of file system inode problem processing
- 力扣刷题 101. 对称二叉树
- Storage scheme of video viewing records of users in station B
- Kettle--控件解析
- Window analysis function last_ VALUE,FIRST_ VALUE,lag,lead
- Oracle modify default temporary tablespace
- Test the time required for Oracle library to create an index with 7 million data in a common way
- Special window function rank, deny_ rank, row_ number
- Apache Atlas Compilation and installation records
- Oracle告警日志alert.log和跟踪trace文件中文乱码显示
猜你喜欢
Android 面试主题集合整理
【报名】TF54:工程师成长地图与卓越研发组织打造
Search ideas and cases of large amount of Oracle redo log
OSS cloud storage management practice (polite experience)
What is the difference between blue-green publishing, rolling publishing and gray publishing?
Elmo (bilstm-crf + Elmo) (conll-2003 named entity recognition NER)
Jenkins construction and use
Solution of discarding evaluate function in surprise Library
Dolphin scheduler configuring dataX pit records
Detailed explanation of redis (Basic + data type + transaction + persistence + publish and subscribe + master-slave replication + sentinel + cache penetration, breakdown and avalanche)
随机推荐
Solution of discarding evaluate function in surprise Library
2021年秋招,薪资排行NO
Ora-16047 of a DG environment: dgid mismatch between destination setting and target database troubleshooting and listening vncr features
FDFS start
Oracle clear SQL cache
剑南春把文字游戏玩明白了
Get the attribute value difference between two different objects with reflection and annotation
零拷貝技術
Technologie zéro copie
RAC environment alert log error drop transient type: systp2jw0acnaurdgu1sbqmbryw = = troubleshooting
cnpm的诡异bug
try --finally
Handling of high usage of Oracle undo
Android 面试主题集合整理
【报名】TF54:工程师成长地图与卓越研发组织打造
Core concepts of microservice architecture
[code analysis (6)] communication efficient learning of deep networks from decentralized data
Using Jupiter notebook in virtual environment
MySQL [acid + isolation level + redo log + undo log]
Reading notes: meta matrix factorization for federated rating predictions