C - Connect Cities
[Q} https://atcoder.jp/contests/abl/tasks/abl_c
1. 連結成分を求められれば、連結成分-1本の道路ですべての街をつなぐことができる。
Q. 連結成分？
A. UnionFindというアルゴリズムを使って求めます。
きれいな構造体とかライブラリが、調べれば出てくるので、コピペして使うのがいいです。
けど、あえて切り出して実装。
/*
3つ必要。
親の管理と、rootをとる関数と、uniteする関数。
*/
// par[i] = 親
// 初期値はpar[0]=0, par[1]=1, par[2]=2...
ll par[100010];
/*
0
/ \
1 2
\
3 という連結成分があった場合
par[0] = 0
par[1] = 0
par[2] = 0
par[3] = 0
になる。
*/
ll root(ll v){
if (par[v] == v) return v;
par[v] = root(par[v]); // 再帰的に親入れ
return par[v] ;
}
/*
0 2
/ \
1 3 2つの連結成分があったら、
par[0] = 0
par[1] = 0 // 0 に属する
par[2] = 2
par[3] = 2 // 2 に属する
unite(0, 2) をすると
0 - 2
/ \
1 3
となるので、
par[0] = 0
par[1] = 0
par[2] = 0
par[3] = 2 // uniteでは、連結成分のまとめnodeだけが統一されるので(2が0にあつまった）
// もともと2群の「子」たちは2のまま。
// 今後、root(3)を参照したときにpar[3] = 0 になる
*/
void unite(ll a, ll b){
ll ra = root(a);
ll rb = root(b);
if (ra == rb) return ; // 同じ親ならunite不要
if (ra > rb) swap(ra, rb);
par[rb] = ra; // rb群 を ra群 に統一。 値の小さい親によせる
}
int main(){
cincout();
ll N, M;
cin >> N >> M;
rep(i, N) par[i] = i; // 親の初期入れ
rep(i, M){
ll a, b;
cin >> a >> b;
--a, --b; // 0-indexed
unite(a, b);
}
// 連結成分-1が答えになる
bool seen[N]{};
ll renketsu = 0;
rep(i, N){
ll r = root(i);
if (seen[r] == true) continue;
seen[r] = true;
++renketsu;
}
cout << renketsu - 1 << endl;
}