D - 連結 / Connectivity

解き直したら解けなかったので、ここで供養します

問題文

atcoder.jp

解法

頂点について考える.と鉄道で連結な頂点集合,高速道路で連結な頂点集合をとする.
求めるべき答えは を満たすの個数である.
頂点集合を構築するにはunionfindを用いればよい.
の個数を愚直に数え上げるとTLEするので工夫する.
具体的には、頂点が属する頂点集合とは一意に定まる.
したがって、これらの をkeyとする連想配列を用いて、数え上げると良い.
ちなみに、下記unionfindはfindで親(集合のID)を返すので、それで管理している.

#include<bits/stdc++.h>
using namespace std;
class unionfind {
    vector<int> par, rank, size_;
public:
    unionfind(int n) :par(n), rank(n), size_(n, 1) {
        iota(par.begin(),par.end(), 0);
    }
    int find(int x) {
        if (par[x] == x)return x;
        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])swap(x, y);
        par[y] = x;
        size_[x] += size_[y];
        if (rank[x] == rank[y])rank[x]++;
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    int size(int x) {
        return size_[find(x)];
    }
};

signed main(){
    int N,K,L;
    cin >> N >> K >> L;
    auto t = unionfind(N);
    auto c = unionfind(N);
    for(int i = 0; i < K; ++i){
        int a,b; cin >> a >> b;
        --a,--b;
        t.unite(a,b);
    }
    for(int j = 0; j < L; ++j){
        int a,b; cin >> a >> b;
        --a,--b;
        c.unite(a,b);
    }
    map<pair<int,int>,int>cnt;
    for(int i = 0; i < N; ++i){
        cnt[make_pair(t.find(i), c.find(i))] += 1;
    }
    for(int i = 0; i < N; ++i)
        cout << cnt[make_pair(t.find(i),c.find(i))]<< endl;
}