Roads and Libraries

• Time : O(clogn)
• Space : O(n)

c++

int uf[100001];
int find(int u) {
    return u == uf[u] ? u : uf[u] = find(uf[u]);
}
void uni(int u, int v) {
    int pu = find(u), pv = find(v);
    uf[pu] = uf[pv] = min(pu, pv);
}
long roadsAndLibraries(long long n, long long lib, long long road, vector<vector<int>> cities) {
    if(lib <= road) return lib * n;
    for(int i = 1; i <= n; i++) uf[i] = i;
    long long res = 0;
    for(auto& c : cities) {
        int u = c[0], v = c[1];
        if(find(u) != find(v)) {
            uni(u, v);
            res += road;
        }
    }
    unordered_set<int> us;
    for(int i = 1; i <= n; i++) us.insert(find(i));
    return res + us.size() * lib;
}