HackerEarth City and Flood problem solution

In this HackerEarth City and Flood problem solution, Fatland is a town that started with N distinct empires, namely empires 1, 2, …, N. But over time, the armies of some of these empires have taken over other ones. Each takeover occurred when the army of empire i invaded empire j. After each invasion, all of empire j became part of empire i, and empire j was renamed as empire i.

Empire Huang, leader of Badland, wants to invade Fatland. To do this, he needs to calculate how many distinct empires still remain in Fatland after all the takeovers. Help him with this task.

HackerEarth City and Flood problem solution.

idx=[]
size=[0]*100
def root(x):
    while x!=idx[x]:
        idx[x]=idx[idx[x]]
        x=idx[x]
    return x

def connected(p, q):
    return root(p)==root(q)

def union(p, q):
    i=root(p)
    j=root(q)

    if size[i]<size[j]:
        idx[i]=j
        size[j]+=size[i]
    else:
        idx[j]=i
        size[i]+=size[j]

n = int(input())
k = int(input())
for i in range(n):
    idx.append(i)
for i in range(k):
    x, y = map(int, input().split(' '))
    union(x-1, y-1)

print(len(set([root(i) for i in idx])))

Second solution

#include <bits/stdc++.h>

using namespace std;

void optimizeIO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int maxn = 1e5;
const int maxk = 1e5;
const int lim = 1e5 + 1;

int parent[lim];

int ancestor(int a)
{
    if (a != parent[a])
        parent[a] = ancestor(parent[a]);
    return parent[a];
}

void merge(int a, int b)
{
    a = ancestor(a);
    b = ancestor(b);
    if (a != b)
        parent[a] = b;
}

int main()
{
    optimizeIO();

    int n, k;
    cin >> n >> k;

    assert(1 <= n and n <= maxn);
    assert(1 <= k and k <= maxk);

    for (int i = 1; i <= n; i++)
        parent[i] = i;

    for (int i = 1; i <= k; i++)
    {
        int city1, city2;
        cin >> city1 >> city2;
        assert(1 <= city1 and city1 <= n);
        assert(1 <= city2 and city2 <= n);
        merge(city1, city2);
    }

    for (int i = 1; i <= n; i++)
        parent[i] = ancestor(i);

    set<int> representativeElements;

    for (int i = 1; i <= n; i++)
        representativeElements.insert(parent[i]);

    int ans = (int) representativeElements.size();

    cout << ans;
    return 0;
}

HackerEarth City and Flood problem solution

HackerEarth City and Flood problem solution.

Second solution

Leave a Reply

Pages

Practice