Link: D. Harmonious Graph

D. Harmonious Graph

You're given an undirected graph with n nodes and m edges. Nodes are numbered from 1 to n.

The graph is considered harmonious if and only if the following property holds:

For every triple of integers (l,m,r) such that 1≤l<m<r≤n, if there exists a path going from node l to node r, then there exists a path going from node l to node m.
In other words, in a harmonious graph, if from a node l we can reach a node r through edges (l<r), then we should able to reach nodes (l+1),(l+2),…,(r−1) too.

What is the minimum number of edges we need to add to make the graph harmonious?

The first line contains two integers n and m (3≤n≤200 000 and 1≤m≤200 000).

The i-th of the next m lines contains two integers ui and vi (1≤ui,vi≤n, ui≠vi), that mean that there's an edge between nodes u and v.

It is guaranteed that the given graph is simple (there is no self-loop, and there is at most one edge between every pair of nodes).

Print the minimum number of edges we have to add to the graph to make it harmonious.

14 8
1 2
2 7
3 4
6 3
5 7
3 8
6 8
11 12
200000 3
7 9
9 8
4 5
In the first example, the given graph is not harmonious (for instance, 1<6<7, node 1 can reach node 7 through the path 1→2→7, but node 1 can't reach node 6). However adding the edge (2,4) is sufficient to make it harmonious.

In the second example, the given graph is already harmonious.

Problem solving:



#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int       f[maxn];
int find(int x)
    return f[x] != x ? f[x] = find(f[x]) : x;
void join(int x, int y)
    x = find(x), y = find(y);
    if (x != y)
        if (x < y)
            swap(x, y);
        f[x] = y;
int main()
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        f[i] = i;
    for (int i = 0, u, v; i < m; i++)
        cin >> u >> v;
        join(u, v);
    int ans = 0, mid = find(n);
    for (int i = n; i >= 1; i--)
        if (i < mid)
            mid = find(i);
        else if (find(i) != mid)
            join(i, mid), ans++;
        mid = min(find(i), mid);
    cout << ans << endl;
    return 0;