# HackerEarth Classic task problem solution

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.

`#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 500002int 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;}`