当前位置:网站首页>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