Harmonious Graph
好后悔在写这个题之前浪费了几分钟时间,不然我就写出来了....
因为他就是连通块之间的合并问题,所以就用并查集就好了
复杂度好像也只是线性的吧...
然后就A了
代码:
// Created by CAD on 2019/12/4.
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int f[maxn];
int find(int x)
{
return x==f[x]?x:f[x]=find(f[x]);
}
int last[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,m; cin>>n>>m;
for(int i=1;i<=n;++i)
f[i]=i;
for(int i=1,u,v;i<=m;++i)
{
cin>>u>>v;
int f1=find(u),f2=find(v);
if(f1!=f2)
f[f1]=f2;
}
int ans=0;
for(int i=1;i<=n;++i)
{
int t=find(i);
if(last[t])
{
for(int j=last[t]+1;j<i;j++)
{
int temp=find(j);
if(temp!=t)
f[temp]=t,ans++;
}
}
last[t]=i;
}
cout<<ans<<endl;
return 0;
}