最小生成树，两节点编号都＞k的直接连边，否则累计不满足这种情况的边的数量len，对这些边建生成树，这len条边中不在生成树上的边就是最少要删去的边 （证明的话因为如果成环了那无论删那条边都是一样的吧..我是这样理解的）
code：
#include<map>#include<set>#include<deque>#include<queue>#include<stack>#include<cmath>#include<ctime>#include<bitset>#include<string>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>#include<climits>#include<complex>#include<iostream>#include<algorithm>#define ll long longusing namespace std;void read(int &x){ char c; while(!((c=getchar())>='0'&&c<='9')); x=c-'0'; while((c=getchar())>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0';}void up(int &x,int y){if(x<y)x=y;}const int maxn = 1100000;const int maxm = 2100000;int fa[maxn],n,m,k;int find_(int x){ if(fa[x]==x) return x; return fa[x]=find_(fa[x]);}int d[maxm][2],len;int main(){ read(n); read(m); read(k); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++) { int x,y; read(x); read(y); if(x>k&&y>k) fa[find_(x)]=find_(y); else len++,d[len][0]=x,d[len][1]=y; } int s=0; for(int i=1;i<=len;i++) { int x=d[i][0],y=d[i][1]; int f1=find_(x), f2=find_(y); if(f1!=f2) fa[f1]=f2,s++; } PRintf("%d/n",len-s); return 0;}新闻热点
疑难解答
