In this HackerEarth Classic task problem solution Given an undirected graph with n vertices. There are m sets of edges in this graph, the set is represented by 2 integers (li,ri) meaning that there are edges (li,ri), (li+1,ri-1), ...(ri,li) in the graph.
Find the number of connected components in this graph.


HackerEarth Classic task problem solution


HackerEarth Classic task problem solution.

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = (int)(1e6) + 5;
int f[N];
int get(int k)
{
return k == f[k] ? k : f[k] = get(f[k]);
}
vector < pii > e[55];
int solve(int n,vector < pii > edges)
{
for (int i = 0;i <= 20;++i)
e[i].clear();
int lg = 0;
while (n >> (lg + 1)) ++lg;
int m = edges.size();
for (auto it : edges)
{
int l1 = it.fi,r1 = it.se;
int l2 = (n - r1 + 1) + n;
int r2 = (n - l1 + 1) + n;
for (int t = lg;t + 1;--t)
if (l2 + (1 << t) - 1 <= r2)
e[t].pb(mp(l1,l2)),l2 += (1 << t),l1 += (1 << t);
}
for (int t = lg;t >= 0;--t)
{
for (int i = 1;i <= n + n;++i)
f[i] = i;
for (auto it : e[t])
f[get(it.fi)] = get(it.se);
if (!t) break;
for (int i = 1;i <= n + n;++i)
if (i != get(i))
e[t - 1].pb(mp(i,get(i))),e[t - 1].pb(mp(i + (1 << (t - 1)),get(i) + (1 << (t - 1))));
e[t].clear();
}
for (int i = 1;i <= n;++i)
f[get(i)] = get(n + n - i + 1);
set < int > ss;
for (int i = 1;i <= n + n;++i)
ss.insert(get(i));
return (ss.size());
}
int main(void)
{
srand(time(0));
int n,m;
scanf("%d%d",&n,&m);
vector < pii > edges(m);
for (auto &it : edges)
scanf("%d%d",&it.fi,&it.se);
cout << solve(n,edges) << '\n';
return 0;
}

Second solution

#include "bits/stdc++.h"
using namespace std;

#define MAX 500002

int n;
int m;


vector<int> rng;

vector<pair<int, int> > query[20];

int belong[MAX * 2];
inline int root(int b) {
if (belong[b] == -1) {
return b;
}
belong[b] = root(belong[b]);
return belong[b];
}
void merge(int a, int b) {
a = root(a);
b = root(b);
if (a == b)return;
if (a > b) {
swap(a, b);
}
belong[b] = a;
}
int main() {
cin >> n >> m;
assert(1 <= n&&n <= 500000);
assert(1 <= m&&m <= 100000);
for (int i = 0; i < 20; i++) {
if (1) {
rng.push_back(1 << i);
}
}
for (int i = 0; i < m; i++) {
int a, b;
scanf("%d%d", &a, &b);
a--;
b--;
assert(0 <= a&&a<n);
assert(0 <= b&&b<n);
assert(a <= b);
int reva = n - a - 1;
int revb = n - b - 1;
swap(reva, revb);
while (a <= b) {
int r = b - a + 1;
int id = upper_bound(rng.begin(), rng.end(), r) - rng.begin();
id--;
query[id].push_back(make_pair(a, reva + n));
a += rng[id];
reva += rng[id];
}
}
int id = upper_bound(rng.begin(), rng.end(), n) - rng.begin();
id--;
for (int x = id; x >= 0; x--) {
memset(belong, -1, sizeof(belong));
for (int j = 0; j < query[x].size(); j++) {
merge(query[x][j].first, query[x][j].second);
}
int RNG = rng[x];
if (RNG > 1) {
for (int j = 0; j <= n - RNG; j++) {
int R = root(j);
if (R != j) {
query[x - 1].push_back(make_pair(j, R));
query[x - 1].push_back(make_pair(j + RNG / 2, R + RNG / 2));
}
}
for (int j = n; j <= n - RNG + n; j++) {
int R = root(j);
if (R != j) {
query[x - 1].push_back(make_pair(j, R));
query[x - 1].push_back(make_pair(j + RNG / 2, R + RNG / 2));
}
}
}
}
for (int j = 0; j < n; j++) {
int rv = n - j - 1;
rv += n;
merge(j, rv);
}
int ans = 0;
for (int j = 0; j < n * 2; j++) {
if (root(j) == j) {
ans++;
}
}
cout << ans << endl;
return 0;
}