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:
  1. Two groups find each other, and the leader of the first group steps down
  2. A becomes the leader of his group
  3. 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;
}