C - Association for Control Over Minds (并查集+vector)

    科技2022-07-12  120

    #include<bits/stdc++.h> using namespace std; const int N=5e5+100; int p[N]; int num[N]; vector<int> v; int find(int x){ if(p[x]!=x) p[x]=find(p[x]); return p[x]; } void he(int x,int y){ int xx=find(x); int yy=find(y); if(xx!=yy){ p[xx]=yy; num[yy]+=num[xx]; } } int main(){ int n;scanf("%d",&n); for(int i=0;i<N;i++){ p[i]=i; num[i]=1; } int ans=0; for(int i=1;i<=n;i++){ v.clear(); int x;scanf("%d",&x); int y; for(int j=0;j<x;j++){ scanf("%d",&y); v.push_back(find(y)); } sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); int s=v.size(); int tt=0; for(int j=0;j<s;j++){ tt+=num[v[j]]; } if(tt==x){ ans++; for(int j=0;j<s;j++){ he(v[j],v[0]); } } } printf("%d\n",ans); return 0; }

     

    Processed: 0.010, SQL: 8