并查集板子。

思路

一条边如果没有我们所关注的点，可以直接不管，因为这些边不会影响我们需要的点。直接丢到并查集里维护即可。

剩下的边贪心，能加的都要加。

代码解释

首先，$u_i>k$ 且 $v_i>k$ 的边一定要选，用并查集维护即可。

1
2
3
4
5
for(int i=1;i<=m;i++){
    cin>>u[i]>>v[i];
    if(u[i]>v[i]) swap(u[i],v[i]);
    if(u[i]>k&&v[i]>k) f[fd(u[i])]=fd(v[i]);
}

然后，剩下 $u_i \le k$ 或 $v_i \le k$ 的边看情况选：

  1. 如果他们不在一个集合里（不会出现简单环），选并合并。
  2. 如果他们在一个集合里，不选并计入答案。
1
2
3
4
5
6
for(int i=1;i<=m;i++){
    if(u[i]<=k||v[i]<=k){
        if(fd(u[i])!=fd(v[i])) f[fd(u[i])]=fd(v[i]);
        else ans[++tot][0]=u[i],ans[tot][1]=v[i];
    }
}

代码楼上楼下都已经写的很明白了，我就不在赘述了。