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.

`#include <bits/stdc++.h>using namespace std;#define MAXN 100005int 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;}`