Amazon Alexa SDE Hiring Challenge

Kingdom Connections

Kingdom Connections

There are N provinces [1, 2, …, N]. King Bab wants to create his kingdom. For this, he needs to capture some provinces. Two provinces can be connected by water, land, or by both. A pair of provinces are connected by land and B pairs of provinces are connected by water. Since bob’s navy is very weak, he does not want any of his captured provinces to be connected by water, moreover Bob has a strong army, so he wants to capture every province that is connected to his kingdom by land.

More formally, the following conditions must be satisfied:

• For each captured province every province connected to it by land should also be captured.
• No two provinces captured should be connected by water directly or by and other provinces.
• Any two captured provinces should be connected directly or through other captured provinces.

Task

Output the maximum number of provinces that Bob can capture satisfying the given conditions. If bob can’t capture any province then output 0.

Solution

• Time : O((n + a + b)logn)
• Space : O(n)

#include <bits/stdc++.h>

#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("Ofast")//Comment optimisations for interactive problems (use endl)
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

struct PairHash {inline std::size_t operator()(const std::pair<int,int> & v) const {return v.first*31+v.second;}};

#define MAX_N 101010
#define INF 987654321
#define EPS 1e-9
#define ll long long
#define pll pair<ll, ll>
#define vpll vector<pll>
#define vall3 vector<array<ll,3>>
#define all3 array<ll,3>
#define all5 array<ll,5>
#define vall5 vector<all5>
#define vll vector<ll>
#define vi vector<int>
#define vs vector<string>
#define usll unordered_set<ll>
#define uspll unordered_set<pll, PairHash>
#define umll unordered_map<ll,ll>
#define vvs vector<vs>
#define vvll vector<vll>
#define all(a) begin(a), end(a)
#define rall(a) rbegin(a), rend(a)

ll __gcd(ll x, ll y) { return !y ? x : __gcd(y, x % y); }

using namespace std;

ll find(vll& uf, ll u) {
    return uf[u] == u ? u : uf[u] = find(uf, uf[u]);
}

void uni(vll& uf, ll u, ll v) {
    ll pu = find(uf, u), pv = find(uf, v);
    uf[pu] = uf[pv] = min(pu, pv);
}

ll solve(vpll& A, vpll& B, ll n) {
    vll wuf(n + 1), luf(n + 1);
    for(ll i = 1; i <= n; i++) wuf[i] = luf[i] = i;

    for(auto& [u, v] : B)
        uni(wuf, u, v);

    for(auto& [u, v] : A) {
        uni(luf, u, v);
    }


    ll res = 0;
    unordered_map<ll, ll> lufc;
    unordered_map<ll, usll> wufc;
    for(ll i = 1; i <= n; i++) {
        ll lp = find(luf, i);
        ll wp = find(wuf, i);
        lufc[lp]++;
        wufc[lp].insert(wp);
    }
    for(auto& [k, v] : lufc) {
        if(v <= res) continue;
        if(wufc[k].size() != v) continue;
        res = v;
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(0);
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll tc = 1;
    cin>>tc;
    for(ll i = 1; i <= tc; i++) {
        ll n, a, b;
        cin>>n>>a>>b;
        vpll A(a), B(b);
        for(ll j = 0; j < a; j++) cin>>A[j].first>>A[j].second;
        for(ll j = 0; j < b; j++) cin>>B[j].first>>B[j].second;
        cout<<solve(A, B, n)<<endl;
    }
    return 0;
}