题解：SP131 SQDANCE - Square dance

· · 题解

SP131 SQDANCE - Square dance 题解

思路

并查集板子。 先把每个的祖先都设为自己。

在合并时，我们只需要将一个的祖先由自己改为另一个祖先。 在查询时，只需看两个点的祖先是否一样。

若可以加边，就合并并查集。

判断是否在一个连通块内就行了，如果是，再加一条边就会变成环。

Code

#include <bits/stdc++.h>
using namespace std;
int fa[100010],n,q,t,s,x,y;
int f(int a){
    if(a==fa[a]) 
        return a;
    return f(fa[a]);
}
int main(){
    cin>>t;
    while(t--){
        s=0;
        scanf("%d%d",&n,&q);
        for(int i=1;i<=n;i++) 
            fa[i]=i;
        while(q--){
            scanf("%d%d",&x,&y);
            if(f(x)==f(y)) 
                s++;
            else 
                fa[f(x)]=f(y);
        }
        cout<<s<<endl;
    }
    return 0;
}