题解 P1551 【亲戚】

## 没错 我又来发题解了（~~虽然前两次都没通过~~，但是我的自信心任然存在，哈哈哈） 题目很简单，解释都在下面了 ``` #include<bits/stdc++.h>//万能头 using namespace std; int f[10000];//father存父亲根 int find(int); int main() { int n,m,k,x,y; cin>>n>>m>>k; for(int i=1;i<=n;i++) { f[i]=i;//开始自己是自己的祖先 } for(int i=1;i<=m;i++) { cin>>x>>y; int xf,yf; xf=find(x); yf=find(y); if(xf!=yf) f[xf]=yf; } for(int i=1;i<=k;i++) { cin>>x>>y; int xf,yf; xf=find(x);//找祖先啦 yf=find(y); if(xf==yf)cout<<"Yes"<<endl;//找到同样的祖先那肯定是亲戚啦 else cout<<"No"<<endl;//不然就不是 } return 0; } int find(int x)//直到找到集合代表，也就是自己是自己的祖先 { if(x==f[x]) return x;//找到啦 return f[x]=find(f[x]);//重点改进，压缩路径，可以省时间，虽然不加也不会超时 }