根本不用并查集
by hyh0926 @ 2024-03-11 18:49:24
@[hyh0926](/user/742030) 是的。而且dfs可以做到严格线性。
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,p,vis[5005];
vector<int>e[5005];
void dfs(int i,int val) {
vis[i]=val;
for(auto j:e[i]) {
if(!vis[j]) {
dfs(j,val);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m>>p;
for(int i=1; i<=m; i++) {
int u,v;
cin>>u>>v;
e[u].emplace_back(v);
e[v].emplace_back(u);
}
for(int i=1; i<=n; i++) {
if(!vis[i]) {
dfs(i,i);
}
}
for(int i=1; i<=p; i++) {
int a,b;
cin>>a>>b;
if(vis[a]==vis[b]) {
cout<<"Yes\n";
} else {
cout<<"No\n";
}
}
return 0;
}
```
by 董乐山2020 @ 2024-03-22 20:40:31