[CSES] Road_Construction | C++

https://cses.fi/problemset/task/1676/

CSES - Road Construction

 

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

const int N = 200001;

class UFDS {
private:
    vector<int> p, rank, setSizes;
    int numSets;
public:
    UFDS(int N) {
        numSets = N;
        rank.assign(N, 0);
        p.assign(N, 0);
        for (int i = 0; i < N; i++) p[i] = i;
        setSizes.assign(N, 1);
    }
    int findSet(int i) {
        return (p[i] == i) ? i : p[i] = findSet(p[i]);
    }
    bool isSameSet(int i, int j) {
        return findSet(i) == findSet(j);
    }
    void unionSet(int i, int j) {
        if (!isSameSet(i, j)) {
            int x = findSet(i), y = findSet(j);
            if (rank[x] > rank[y]) {
                setSizes[findSet(x)] += setSizes[findSet(y)];
                p[y] = x;
            }
            else {
                setSizes[findSet(y)] += setSizes[findSet(x)];
                p[x] = y;
                if (rank[x] == rank[y])
                    rank[y]++;
            }
            numSets--;
        }
    }
    int setSize(int i) {
        return setSizes[findSet(i)];
    }
    int numDisjointSets() {
        return numSets;
    }
};
int main() {
	int n, a, b, m;
	cin >> n >> m;

    UFDS ufds{ n };

    int cc = n;
    int mx = 1;
    while (m--) {
        cin >> a >> b;
        a--;
        b--;
        if (ufds.findSet(a) != ufds.findSet(b)) {
            ufds.unionSet(a, b);
            int union_set = ufds.setSize(a);
            mx = max(mx, union_set);
            cc--;
        }
        cout << cc << " " << mx << endl;
    }
 
}

 

연결할 때마다, 두 마을 이 포함된 set 을 union 한 뒤, 해당 set 의 rank를 반환하는 형태이다.

문제에서 입력 제한 값이 매우 크므로 전체 마을을 검사하는 것은 시간초과가 날 가능성이 매우 크므로 Union Find 형태로 푸는 것이 적절하다.