【題解】CSES 1676 Road Construction

【題目敘述】https://cses.fi/problemset/task/1676/
【解題想法】並查集

#include <iostream>
#include <cstring>
using namespace std;
 
int n, m, a, b, p[100005], mx, cnt;
 
int f(int x){
    if (p[x] < 0) return x;
    else return p[x] = f(p[x]);
}
 
int main() {
    cin >> n >> m;
    memset(p, -1, sizeof(p));
    mx = 1;
    cnt = n;
    while (m--){
        cin >> a >> b;
        a = f(a);
        b = f(b);
        if (a != b){
            p[a] += p[b];
            mx = max(mx, -p[a]);
            p[b] = a;
            cnt--;
        }
        cout << cnt << " " << mx << "\n";
    }
}
分享本文 Share with friends