题目链接: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;
}