Codeforces Round #600 (Div. 2)D. Harmonious Graph

题目链接：https://codeforces.com/contest/1253/problem/D
题意：若某个节点编号到大于他的编号的节点，那么他们之间的任意一个点也要可达。
题目思路：开始的时候想的是一个加权并查集，权维护的是最远的点，这和后来的正解做法思路确实是反了，直接把父亲节点当做是当前节点的最远节点即可。
要说有什么教训，我感觉太多了，思路出来以后，一定要思考他的正确性，千万别吊死在一个思路上，不知道为什么自己总是能想出的思路却总是不合理的想，思考要细致啊！上一次D题就是如此，一定要静下心来，不能浮躁，切忌浮躁。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+9;
int fa[maxn];
int findx(int x)
{
    if(x==fa[x])return x;
    return fa[x]=findx(fa[x]);
}
void merges(int a,int b)
{
    int x=findx(a),y=findx(b);
    if(x!=y)
    {
        fa[x]=max(x,y);
        fa[y]=max(x,y);
    }
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
    {
        fa[i]=i;
    }
    for(int i=1; i<=m; i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        merges(x,y);
    }
    int ans=0;
    for(int i=1; i<=n; i++)
    {
        int maxx=findx(i);
        if(maxx!=i)
        {
            for(int j=i+1; j<=maxx; j++)
            {
                int q=findx(j);
                if(q!=maxx)
                {
                    ans++;
                    fa[q]=max(maxx,fa[q]);
                    fa[maxx]=max(maxx,fa[q]);
                    maxx=max(maxx,fa[q]);
                }
            }
            i=maxx;
        }
    }
    cout<<ans<<endl;
    return 0;
}