Codeforces Round 600 (Div. 2) - D. Harmonious Graph
Link: D. Harmonious Graph
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?
Input
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).
Output
Print the minimum number of edges we have to add to the graph to make it harmonious.
Examples
input
14 8
1 2
2 7
3 4
6 3
5 7
3 8
6 8
11 12
output
1
input
200000 3
7 9
9 8
4 5
output
0
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→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:
这道题的意思是给你一张图可能是不连通的图。每个顶点都有一个编号。规定一种特殊的图：这个图中如果从顶点i可以到达顶点j，并且如果存在一个数k(i<k<j)，那么i也应该可以到达k。现在给你一个图，问你至少需要再加几条边可以让这个图变成规定的那种特殊的图。
一开始毫无思路，最后还是靠bly过了这道题。吹爆bly。
我们通过并查集把输入的有边的顶点连在一起，此时父节点是同一个顶点的点是可以相互到达的。
我们每次都让最小的顶点做一个连通块的父节点。首先对一个中间变量赋值为节点n的父节点，然后从n开始遍历每一个顶点，如果当前顶点的值小于那个中间变量，说明他和上一个连通块没有关系。就对mid的值进行更新。然后如果出现i>=mid的情况，就看这个节点的父节点跟不跟mid相等，如果不相等就连一条边连起来，答案加一。然后更新一下mid的最小值，因为我们一直是以最小的点作为父节点。
Code:
#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()
{
ios::sync_with_stdio(0);
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;
} 
