写这道题的时候真没有什么思路，但是注意到题目中说“如果从节点 \(l\) 可以通过若干条边到达节点 \(r\)（且 \(l < r\)），那么从 \(l\) 到 \((l+1)，(l+2)，\ldots，(r-1)\) 的所有节点也都必须可达”。那么容易想到并查集。用并查集来求得初始所有点及边构成的不同的联通块之后进一步想：对于两个同处于一个连通块的点 \(i,j\)，那么任意的点 \(m\) 满足 \(i<m<j\) 就必须与 \(i\) 与 \(j\) 所在的连通块连通。
我们先利用并查集求出每个点所在的连通块：
cin>>n>>m;for(int i=1;i<=n;i++)fa[i]=i;for(int i=1;i<=m;i++){cin>>a>>b;merge(a,b);}for(int i=1;i<=n;i++){f[i]=find(i);//求个点所在的连通块，比如说，若f[i]==f[j]则点i与j处于同一个连通块}
分析以下样例：
输入：
14 8
1 2
2 7
3 4
6 3
5 7
3 8
6 8
11 12
那么我们以此求得的 \(f_i\) 分别为：
Node: 1 2 3 4 5 6 7 8 9 10 11 12 13 14
f[i]: 7 7 8 8 7 8 7 8 9 10 12 12 13 14
依据题意，因为点8与点3联通，而点8与点3之间的点7不在同一个连通块，所以应在点7所在的连通块与点8所在的连通块连一条边，这样整个图就和谐了。
据以上分析可以得出，我们在求出每个点所在的连通块后，可以维护每个连通块所包含的点的最大的点与最小的点（即每个连通块所在的 \(f_i\) 的左界与右界），然后通过合并有左右界有重叠的连通块，再通过新的连通块继续合并，记录合并次数则可以得出答案。
以分析上一个样例为例，我们求出每个连通块的左界与右界：
连通块 左界 右界7 1 78 3 89 9 910 10 1012 11 12
| 连通块 | 左界 | 右界 |
|---|---|---|
| 7 | 1 | 7 |
| 8 | 3 | 8 |
| 9 | 9 | 9 |
| 10 | 10 | 10 |
| 12 | 11 | 12 |
| 13 | 13 | 13 |
| 14 | 14 | 14 |
可以看到，联通块7的范围与连通块8的范围有重叠部分（即点3到点7），那么则代表连通块7存在一个点 \(i\) 与\(j\) 联通，但不与连通块8中的点 \(r\) 联通（\(i < r < j\)），那么我们就需要在连通块8与连通块7之间连边，最后得到的新连通块左界为 \(1\)，右界为 \(8\)，经判断，已没有更多连通块有重大，所以答案为 \(1\)。
\(Code\) :
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
struct Edge{int r;int l;
};
Edge vi[214514];
int vis[214514],dif[214514],su[214514];
int n,m,fa[214514],fi[214514];
int find(int x){if(fa[x]==x)return x;return fa[x]=find(fa[x]);
}
void merge(int x,int y){if(find(x)!=find(y))fa[find(x)]=find(y);
}
vector<int> v;
set<int> s;
int a,b;
int main(){cin>>n>>m;for(int i=1;i<=n;i++)fa[i]=i;for(int i=1;i<=m;i++){cin>>a>>b;merge(a,b);}for(int i=1;i<=n;i++){fi[i]=find(i);if(!vis[fi[i]]){vis[fi[i]]=1;v.push_back(fi[i]);vi[fi[i]]={i,i};}else{vi[fi[i]].l=min(i,vi[fi[i]].l);vi[fi[i]].r=max(i,vi[fi[i]].r);}}
int h=0;for(int i=0;i<v.size()-1;i++){int pre=v[i];int nxt=v[i+1];
if(vi[pre].l<=vi[nxt].r&&vi[pre].l>=vi[nxt].l&&vi[pre].r>vi[nxt].r){h++;vi[nxt].r=vi[pre].r;}else if(vi[nxt].l<=vi[pre].r&&vi[nxt].l>=vi[pre].l&&vi[nxt].r>vi[pre].r){h++;vi[nxt].l=vi[pre].l;}else if(vi[pre].l<=vi[nxt].l&&vi[pre].r>=vi[nxt].r){h++;vi[nxt].l=vi[pre].l;vi[nxt].r=vi[pre].r;}else if(vi[nxt].l<=vi[pre].l&&vi[nxt].r>=vi[pre].r){h++;}} cout<<h;return 0;
}