Submission #1972096

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pint;

#define MAX_N 100001
struct UnionFind{
    int par[MAX_N],rank[MAX_N]; 
    void init(int n){
        for (int i=0;i<n;i++){
            par[i]=i;
            rank[i]=0;
        }
    } 
    int find(int x){
        if (x==par[x]) return (x);
        return (par[x]=find(par[x]));
    }
    void unite(int x, int y){
        x=find(x);y=find(y);       
        if(x==y) return;
        if(rank[x]<rank[y]){
            par[x]=y;
        }
        else{
            par[y]=x;
            if(rank[x]==rank[y]) rank[x]++;
        }
    } 
    bool same(int x, int y){
        return (find(x) == find(y));
    } 
};

set<int> st;
int main(){
    int n,m,ai,bi;
    cin>>n>>m;
    UnionFind uf;
    uf.init(n);
    rep(i,m){
        cin>>ai>>bi;
        --ai,--bi;
        uf.unite(ai,bi);
    }
    int cnt=0;
    rep(i,n){
        st.insert(uf.find(i));
    }
    cout<<st.size()-1<<endl;
    return 0;
}

Submission Info

Judge Result