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;
}