ARC#032 B:道路工事

22個あるケースのうち一つだけ通らないので謎だ…

#include <iostream>
#include <set>
using namespace std;

#define pb push_back 
#define MAX_N 1000000


int par[MAX_N]; // 親
int 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 (par[x] == x) { return x;
  } else {
    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);
}

int main(void){

  int N, M;

  cin >> N >> M;
  init(N);

  while(M--){
    int a,b;
    cin >> a >> b;
    unite(a,b);
  }

  set<int> s;
  for(int i = 1; i <= N; i++){
    s.insert(par[i]);
  }
  
  cout << s.size()-1 << endl;
  return 0;
}