牛客IOI周赛19-普及组 C-小y的旅行

小y的旅行

• 分析

  一个环是一个连通块，每次将两条边合并在一起，求出答案。那么我们该如何合并？既然编号小于等于k的点不能在

  环上，那么我们选择先将端点都大于k的边合并在一起。之后再将剩下的边合并在一起。如果能够合并，那么就不用

  拆边，但是如果成环了，那么我就得把当前这条边删去以保证要求

• 代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;

int n,m,k,ans;
int f[N],x[N],y[N];

inline int find(int x)
{
    if(x==f[x]) return x;
    return f[x]=find(f[x]);
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<=n;i++) f[i]=i;
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
        if(x[i]>k&&y[i]>k) f[find(x[i])]=find(y[i]);
    }
    for (int i=1;i<=m;i++)
    {
        if(x[i]<=k||y[i]<=k)
        {
            int u=find(x[i]);
            int v=find(y[i]);
            if(u==v) ans++;
            f[u]=v;
        }
    }
    printf("%d\n",ans);
    return 0;
}