题目大意：
n个点，m条边，两个数l和r，如果l和r相连接，那么对于l和r之间值任意一个数都要和l相连。问达到这一目的需要添加的边的最小数量。
题解：
我们首先要找到当前连通块中最大的那个点，也就是说所有小于当前点的点都要和这个点相连，如果不相连的话，加一条边，所以用我们可以用一个mark数组来标记当前当前点是否在当前联通块中，如不在的话，并且当前点的大小小于联通块的最大点的大小，我们就要加一条边。可以用dfs来遍历联通块
#include<bits/stdc++.h> using namespace std; const int N=2E5+7; vector<int >ve[N]; int mark[N]; int s=0; void dfs(int x){ mark[x]=1; s=max(s,x); for(int i=0;i<ve[x].size();i++){ int a=ve[x][i]; if(!mark[a]) dfs(a); } } int main(){ int n,m; cin>>n>>m; int x,y; for(int i=1;i<=m;i++) { cin>>x>>y; ve[x].push_back(y); ve[y].push_back(x); } int ans=0; for(int i=1;i<=n;i++){ if(mark[i]) continue ; if(i<s){ ve[i].push_back(s); ve[s].push_back(i); ans++; } dfs(i); } cout<<ans<<endl; return 0; }
太秒啦！！！！
原文：https://www.cnblogs.com/Accepting/p/11919810.html