Harmonious Graph (Codeforces 1253D)
Tags: Greedy, dsu

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 \le l < m < r \le 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), \ldots, (r-1)$$$ too.What is the minimum number of edges we need to add to make the graph harmonious? 

Input: The first line contains two integers $$$n$$$ and $$$m$$$ ($$$3 \le n \le 200\ 000$$$ and $$$1 \le m \le 200\ 000$$$).The $$$i$$$-th of the next $$$m$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$), 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).

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

Note: 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 \rightarrow 2 \rightarrow 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.

Sample Inputs:
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

Sample Outputs:
1

0

Solution (Python):
from collections import deque
(n, m) = map(int, input().split())
a = [[] for i in range(n + 1)]
for i in range(m):
    (x, y) = map(int, input().split())
    a[x].append(y)
    a[y].append(x)
vis = [1] * (n + 1)
count = 0
m = 1
for i in range(1, n + 1):
    if vis[i]:
        if i < m:
            count += 1
        s = deque([i])
        while s:
            x = s.popleft()
            if vis[x]:
                s += a[x]
                vis[x] = 0
                if x > m:
                    m = x
print(count)

Solution (Python):
def main() -> None:
    (n, m) = map(int, input().split())
    a = []
    for i in range(n + 1):
        a.append([])
    for i in range(m):
        (u, v) = map(int, input().split())
        a[u].append(v)
        a[v].append(u)
    used = [0] * (n + 1)
    ans = 0
    con = 1
    for i in range(1, n + 1):
        if not used[i]:
            b = [i]
            if i < con:
                ans += 1
            while len(b):
                tc = b.pop()
                if not used[tc]:
                    b += a[tc]
                    used[tc] = 1
                    if tc > con:
                        con = tc
    print(ans)
main()

Solution (Python):
def main():
    (n, m) = map(int, input().split())
    a = []
    for i in range(n + 1):
        a.append([])
    for i in range(m):
        (u, v) = map(int, input().split())
        a[u].append(v)
        a[v].append(u)
    used = [0] * (n + 1)
    ans = 0
    con = 1
    for i in range(1, n + 1):
        if not used[i]:
            b = [i]
            if i < con:
                ans += 1
            while len(b):
                tc = b.pop()
                if not used[tc]:
                    b += a[tc]
                    used[tc] = 1
                    if tc > con:
                        con = tc
    print(ans)
main()