【題解】AtCoder ACL Beginner Contest C – Connect Cities

【題目敘述】https://atcoder.jp/contests/abl/tasks/abl_c
【解題想法】並查集

#include <iostream>
using namespace std;

int n, m, p[100005], cnt;

int f(int x){
    if (p[x] == x) return x;
    return p[x] = f(p[x]);
}

int main() {
    cin >> n >> m;
    cnt = n;
    for (int i = 1; i <= n; i++){
        p[i] = i;
    }
    for (int i = 0, a, b; i < m; i++){
        cin >> a >> b;
        a = f(a);
        b = f(b);
        if (a != b){
            p[b] = a;
            cnt--;
        }
    }
    cout << cnt-1 << "\n";
}

分享本文 Share with friends