HackerEarth City and Soldiers problem solution

YASH PAL, 31 July 202415 February 2026

In this HackerEarth City and Soldiers problem solution Today, King Trophies is on another rampage to destroy the small village controlled by Alex. Please help his soldiers.

At first, there are N individual soldiers, who haven’t yet joined together; each of these soldiers is the leader of his/her own group. You have to handle 3 types of operations:

Two groups find each other, and the leader of the first group steps down
A becomes the leader of his group
Output the leader of a certain group

HackerEarth City and Soldiers problem solution

HackerEarth City and Soldiers problem solution.

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
int correspond[MAXN];
int parent[MAXN]; 
int findset (int a)
{
    if (parent[a]==0)return a; return parent[a]=findset(parent[a]); 
}
void merge (int a, int b)
{
    int k = findset(a), kk = findset(b); 
    if (k==kk) return;
    parent[k]=kk;   
} 
int main()
{
    for (int g=1; g<MAXN; g++) correspond[g]=g; 
    ios_base::sync_with_stdio(0); 
    int N, Q; cin >> N >> Q;
    for (int g=0; g<Q; g++)
    {
        int T; cin >> T;
        if (T==1)
        {
            int a, b; cin >> a >> b;
            merge(a, b); 
        }
        else if (T==2)
        {
            int a; cin >> a;
            int k = findset(a); 
            swap(correspond[a], correspond[k]); 
        }
        else
        {
            int a; cin >> a; 
            cout << correspond[findset(a)] << 'n';
        }
    }
    return 0; 
}

Second solution

#include <bits/stdc++.h>

using namespace std;

#define si(x) scanf("%d", &x)
#define pi(x) printf("%d", x)

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

int n, q;

vector<int> parent(lim);

void init(int n)
{
    for (int i = 1; i <= n; i++)
        parent[i] = i;
}

int ancestor(int a)
{
    if (parent[a] != 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;
}

void makeleader(int a)
{
    int pa = ancestor(a);
    parent[pa] = parent[a] = a;
}

int main()
{
    si(n), si(q);

    assert(1 <= n and n <= maxn);
    assert(1 <= q and q <= maxq);

    init(n);

    for (int i = 1; i <= q; i++)
    {
        int type, a, b;

        si(type), si(a);

        assert(1 <= type and type <= 3);
        assert(1 <= a and a <= n);

        if (type == 1)
        {
            si(b);
            assert(1 <= b and b <= n);
            merge(a, b);
        }
        else if (type == 2)
        {
            makeleader(a);
        }
        else if (type == 3)
        {
            pi(ancestor(a));
            puts("");
        }
    }
    return 0;
}

coding problems solutions HackerEarth HackerEarth

Leave a Reply