并查集(m次询问n对关系,问p和q有没有关系)
程序员文章站
2022-04-01 10:51:47
前提:x和y有关系,y和z有关系,那么x和z有关系。 现在先给出n(1<=n<=5000)对关系,然后有m(1<=m<=5000)次询问,每次询问给出一个p和q,问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
上一篇: 企业如何做好品牌的软文营销推广?
下一篇: Dubbo学习(四)——多协议支持