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

coding problems