P1551 亲戚题解

· · 题解

题外话

看了看大家各位大佬的做法，都是用并查集（我根本不会用 QAQ），所以我就在想能不能用其他做法，在经过亿点思考后，我尝试了 dfs。

算法分析

题目大意

给出 n 个点和 m 条边，以及 q 次询问，每次询问 i,j 是否在同一个图中。

思路

首先把图存起来（这里我用了 vector)。然后对于每次询问，从 i 点开始遍历，是否能到达 j 点。但是，这样跑时间复杂度极高：O(qnm)，TLE 到自闭。

在上述方法中，我们可以发现：有许多点被遍历了多次，那我们可以把 n 都遍历一次，这样对于每次询问只需要 O(1) 的时间复杂度。

如何遍历呢？我们可以初始化每个人的祖先是自己，对于每次遍历到的两个点，把两人的祖先合并为较小的一个。然后直接遍历 1 \sim n，这虽然能 AC（因为数据太弱了，只有 5000），但是时间复杂度仍然高：O(nm)。

优化

难道我们一定要遍历 n 个点？

显然不是，在同一个图中，只需要遍历最小的那一个，这样这个图中的所有点的祖先就可以合并，也就是说，只有一个点没有被遍历过才需要遍历。时间复杂度：O(n)。

代码参考

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5010;
int n,m,q,a[N];
vector<int> v[N];
void dfs(int x){
    for(auto i:v[x]){
        if(a[i]>a[x]){  //合并为更小的
            a[i]=a[x];
            dfs(i);  //只有没被遍历过才需要搜
        }
    }
    return ;
}
signed main(){
    cin>>n>>m>>q;
    for(int i=1;i<=m;++i){
        int x,y; cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=1;i<=n;++i) a[i]=i;//初始化祖先都是自己
    for(int i=1;i<=n;++i){     //从最小的开始
        if(a[i]==i) dfs(i);   //只有没被遍历过才需要遍历
    }
    while(q--){
        int x,y; cin>>x>>y;
        if(a[x]==a[y]) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}