Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

HackerEarth City and Soldiers problem solution

YASH PAL, 31 July 2024
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;
}
coding problems solutions

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes