题目描述
知识点:并查集的使用,路径压缩,注意find里面用路径压缩p[x]=find[p[x]]
可以减少对空间的利用.
并查集思路:首先将所有子集指向自身p[i]=i
其中p[i]表示的是i的父亲,通过find
函数找到共同的祖先,比较祖先是否相等即可。
这道题注意cin,cout会超时.
样例
blablabla
算法1
(并查集) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20005;
int n,m,q;
int p[N];
int find(int x)
{
if(p[x]!=x) p[x] = find(p[x]);
return p[x];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1;i <= n; i++) p[i]=i;
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
p[find(a)]=find(b);
}
scanf("%d",&q);
while(q--)
{
int a,b;
scanf("%d%d",&a,&b);
if(p[find(a)]==p[find(b)]) puts("Yes");
else puts("No");
}
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla