https://blog.csdn.net/qq_36931762/article/details/88063678?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-1.channel_param&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-1.channel_param
https://blog.csdn.net/qq_40677317/article/details/105160684?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-4.channel_param&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-4.channel_param
本来以为这道题目很简单 只需要注意：都和第一个节点相连就可以 但是搞了一个多小时才出来AC------》一直吸收不了输入的行数 有2个注意点： 1.关于id编号， 他给出了n，是行数/关系数，但是没有给我们最大的编号，这需要我们自己把这些编号都吸收，再求最大值，这样有助于我们后面求组数和每组个数（因为你初始化的时候，范围是10010，每个节点的根节点都不为0，这样不利于后续） 2.关于findFather(i)和father[i]， 在求组数和个数中的使用，一般都在最大编号范围内（从1开始），用findFather[i]!=0为条件，让isRoot[findFather(i)]++,最后在最大编号范围内，求isRoot[i]不为0的个数，即组数
#include <iostream> #include <cstdio> #include <set> using namespace std; const int maxn=10010; int father[maxn]={0}; int isRoot[maxn]={0}; char ans[maxn]; int maxId=0; // void init(int n){ // for(int i=1;i<=n;i++){ // father[i]=i; // } // } int findFather(int x){ if(x==father[x])return x; else{ int F=findFather(father[x]); father[x]=F; return F; } } void Union(int a,int b){ int faA=findFather(a); int faB=findFather(b); if(faA!=faB){ father[faB]=faA; } } int main() { int n,k,p1,pn; cin>>n; // init(n); for(int i=1;i<10010;i++){ father[i]=i; } set<int>s; for(int i=0;i<n;i++){ int k,p1; // scanf("%d %d",&k,&p1); //cin>>k>>p1; scanf("%d", &k); scanf("%d", &p1); s.insert(p1); for(int j=1;j<k;j++){ int pn; scanf("%d",&pn); //cin>>pn; s.insert(pn); Union(p1,pn); } } // while(n--){ // cin>>k; // cin>>p1; // s.insert(p1); // for(int i=1;i<k;i++){ // cin>>pn; // s.insert(pn); // Union(p1,pn); // } // } set<int>::iterator it; for(it=s.begin();it!=s.end();it++){ if(*it>maxId)maxId=*it; } //======================================== cout<<s.size()<<" "; int cnt=0; for(int i=1;i<=maxId;i++){ // if(i==findFather(i)){ // cnt++; // } // if(i==father[i]){ // cnt++; // } if(findFather(i)!=0){ //if(father[i]!=0){ ///isRoot[father[i]]++; isRoot[findFather(i)]++; } } for(int i=1;i<=maxn;i++){ //if(i==father[i]){ // // cnt++; // //} if(isRoot[i]!=0){ cnt++; } } cout<<cnt<<endl; //========================================= int q; cin>>q; for(int i=0;i<q;i++){ int x,y; scanf("%d %d",&x,&y); // if(findFather(x)==findFather(y)){ if(father[x]==father[y]) //ans[i]= cout<<'Y'<<endl; else //ans[i]= cout<<'N'<<endl; } return 0; }