小y的旅行

小y的旅行:

题目要你去除最少的边使得小于k的点里面没有环。不难想到用并查集来写，如果x与y本来在一个没有环的连通块内，如果再在这个连通块内加入一条边，那么一定会构成环，所以并查集判断一下是不是在同一个连通块内就行了。首先把两个点都大于k的边给合并，这个并不影响结果，然后判断里面有小于k的点的合并，如果之前已经在一个连通块内，则不需要加入这条边：即删除这条边，判断一下就是删除最少的边了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
    ll s=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;c=getchar();
    }
    while(c>='0'&&c<='9'){
        s=(s<<1)+(s<<3)+(c^48);c=getchar();
    }
    return f*s;
}
const int N=2555555;
int b[N];
struct f{
    int x,y;
}a[N];
int find(int x){
    if(b[x]!=x)b[x]=find(b[x]);
    return b[x];
}
int main(){
    int n=read(),m=read(),k=read(),ans=0;
    for(int i=1;i<=n;i++)b[i]=i;
    for(int i=1;i<=m;i++){
        a[i].x=read(),a[i].y=read();
        if(a[i].x>k&&a[i].y>k&&find(a[i].x)!=find(a[i].y)){
            b[find(a[i].x)]=find(a[i].y);
        }
    }
    for(int i=1;i<=m;i++){
        int x=a[i].x,y=a[i].y;
        if(x<=k||y<=k){            
            if(find(x)==find(y)){
                ans++;
            }
            else{
                b[find(x)]=find(y);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}