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; }