小A参加了一个n人的活动，每个人都有一个唯一编号i(i>=0 & i<n)，其中m对相互认识，在活动中两个人可以通过互相都认识的一个人介绍认识。现在问活动结束后，小A最多会认识多少人？
算法：并查集
#include<iostream> #include<algorithm> #include<vector> using namespace std; vector<int>f; int find(int x){ return x==f[x]?x:f[x]=find(f[x]); } int main(void){ int n,idx,m; cin>>n>>idx>>m; f=vector<int>(n); for(int i=0;i<n;i++)f[i]=i; int ans(0),b(0); while(m--){ int one, two; scanf("%d,%d", &one, &two); if(one==idx||two==idx)b++; int fx=find(one),fy=find(two); if(fx!=fy)f[fx]=fy; } for(int i=0;i<n;i++) if(find(idx)==find(i))ans++; cout<<ans-b-1<<endl; return 0; }
原文：https://www.cnblogs.com/programyang/p/11147576.html