并查集（m次询问n对关系，问p和q有没有关系）

前提：x和y有关系，y和z有关系，那么x和z有关系。
现在先给出n（1<=n<=5000）对关系，然后有m（1<=m<=5000）次询问，每次询问给出一个p和q，问p和q有没有关系。
直接代码看注释吧。

#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<cstring> using namespace std; typedef long long ll; typedef unsigned long long ull; int n,m,p,f[5005]; //f[i]存的是i的最大父亲 int fd(int x)//找x的最大父亲 { return f[x] == x ? x : (f[x] = fd(f[x])); //x相当于儿子，f[x]相当于父亲 //如果x的f[x]不是自己，说明x上面有父亲 //就fd(f[x])看看x的父亲是不是x的最大父亲 //直到找到最大的父亲,然后将f[x]更新为目前找到的最大父亲(路径优化) } int main() { //std::ios::sync_with_stdio(0); cin >> n >> m >> p; for(int i = 1 ; i <= n ; i ++)//1~n { f[i] = i;//一定要初始化，将自己初始为自己的父亲  } for(int i = 0 ; i < m ; i ++) { int x,y; scanf("%d%d",&x,&y); f[fd(y)] = fd(x); //让x的最大父亲成为y最大父亲的父亲 //相当于将y最大父亲和它的儿子们放到x的最大父亲下面 //即让x的最大父亲成为他们的最大父亲 //这样就能让y的儿子也认x的最大父亲为他们的最大父亲  } for(int i = 0 ; i < p ; i ++) { int x,y; scanf("%d%d",&x,&y); if(fd(x) == fd(y)) printf("Yes\n"); //看看x,y的最大父亲是否一致，如果一致说明他们有关系 else printf("No\n"); } return 0; } 

并查集可以用来在图里找是否有环之类的操作，但我是蒟蒻，图论很菜。。。

本文地址：https://blog.csdn.net/m0_46168750/article/details/107800749