NC212821. 小y的旅行
描述
输入描述
第一行三个正整数n,m,k
接下来m行，每行有两个正整数u,v代表一条无向边
输出描述
一行一个整数代表最少删去的边数
示例1
输入:
11 13 5 1 2 1 3 1 5 3 5 2 8 4 11 7 11 6 10 6 9 2 3 8 9 5 9 9 10
输出:
3
C++(clang++11) 解法, 执行用时: 1387ms, 内存消耗: 31224K, 提交时间: 2020-11-20 00:46:58
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int pre[maxn],u[2*maxn],v[2*maxn],n,m,k,ans;
int xfind(int x){
return pre[x]==x ? x : pre[x]=xfind(pre[x]);
}
int main() {
cin>>n>>m>>k;
for(int i=1;i<=n;i++) pre[i]=i;
for(int i=1;i<=m;i++){
cin>>u[i]>>v[i];
if(u[i]>k&&v[i]>k) pre[xfind(u[i])]=xfind(v[i]);
}
for(int i=1;i<=m;i++){
if(u[i]<=k || v[i]<=k){
int a=xfind(u[i]),b=xfind(v[i]);
if(a==b) ans++;
else pre[a]=b;
}
}
cout<<ans<<endl;
}