Submission #1531587

---

Source Code Expand

#include <iostream>
#include <vector>

#define REP(i,n) for(int i=0; i<n; ++i)

int N, M;

std::vector<int> parent;

void init(int n){
    parent.resize(n);
    REP(i,n){
        parent[i] = i;
    }
}

int root(int x){
    if(parent[x] == x){
        return x;
    }else{
        return parent[x] = root(parent[x]);
    }
}

bool same(int x, int y){
    return root(x) == root(y);
}

void unite(int x, int y){
    x = root(x);
    y = root(y);
    if(x != y){
        parent[x] = y;
    }
}

int main(void){
    std::cin >> N >> M;
    init(N);

    int a, b;
    REP(i,M){
        std::cin >> a >> b;
        unite(--a,--b);
    }

    int cnt = 0, old = 0;
    REP(i,N){
        if( i == 0 || same(old, i) ) continue;

        ++cnt;
        unite(old, i);
        old = i;
    }

    std::cout << cnt << std::endl;
}

Submission Info

Judge Result