题目链接

https://ac.nowcoder.com/acm/contest/7780/C

解题思路

并查集。
大致思路：先把连接着两个大于k的点的边加入，再判断连接着小于等于k的两个点的边，两点是否同根，若同根则答案++，并且不将边加入；若不同根，则答案不变，并且加入边。
两个点，其中存在至少一个点小于等于k，若二者存在边，且同根，说明两点已经相连，若再直接连接二者将形成环，所以ans++。
代码步骤：
第一次循环，初始化每个点的根为自己；
第二次循环，先把两个点都大于k且未相连的边加入；
第三次循环，判断两个点中存在一个点小于等于k的边连接的两个点的根是否相同，若同，ans++；不同，两点相连，加入边。
为什么要先把大于k的边加入，再循环小于等于k的？
举个例子：
图片说明
假设纯黑点为小于等于k的点，空心点为大于k的点。
如果一次循环插入所有边：
若先插入边1，没问题可以插入；再插入边2，依旧可以；此时，要插入边3，但是边3连接的两个点是大于k的点，又因为同根，所以不会ans不会自加，显然错误。

AC代码

#include<bits/stdc++.h>
#define sc(x) scanf("%d",&x)
#define pr(x) printf("%d",x);
using namespace std;
const int N=2e6+100;
int u[N],v[N],fa[N],n,m,k,ans;
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void join(int x,int y){
    int rx=find(x),ry=find(y);
    if(rx!=ry) fa[rx]=ry;
}
int main(){
    sc(n);sc(m);sc(k);
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=1;i<=m;i++){
        sc(u[i]);sc(v[i]);
        if(u[i]>k&&v[i]>k&&find(u[i])!=find(v[i])) join(u[i],v[i]);
    }
    for(int i=1;i<=m;i++){
        if(u[i]<=k||v[i]<=k) {
            int ru=find(u[i]),rv=find(v[i]);
            if(ru==rv) ++ans;
            else join(ru,rv);
        }        
    }
    pr(ans);    
}