对无向边(u,v),其权值为max(u的度数,v的度数) 然后跑一遍kruskal,重写cmp时要注意判断边权相同但是端点不同的情况,让相同起点放在一起,才能保证最后输出答案正确
#include<cstdio> #include<cstring> #include<cmath> #include<string> #include<iostream> #include<vector> #include<map> #include<set> #include<stack> #include<queue> #include<stdlib.h> #include<algorithm> #include<time.h> #define bug1(g) cout<<"test: "<<g<<endl #define bug2(g,i) cout<<"test: "<<g<<" "<<i<<endl #define bug3(g,i,k) cout<<"test: "<<g<<" "<<i<<" "<<k<<endl using namespace std; typedef unsigned long long ll; struct node { int u,v; }a[200005]; int d[200005]; bool cmp(node a,node b) { if(max(d[a.u],d[a.v])!=max(d[b.u],d[b.v])) return max(d[a.u],d[a.v])>max(d[b.u],d[b.v]); else return a.u<b.u; //边权一样,同一结点的边放在一起 } int n,m; int f[2000005]; void init() { for(int i =0;i<200005;i++) f[i]=i; } int fi(int x) { if(f[x]==x) return x; else return f[x]=fi(f[x]); } void un(int a,int b) { f[fi(a)]=fi(b); } int main() { ios::sync_with_stdio(0); cin>>n>>m; init(); for(int i =0;i<m;i++) { cin>>a[i].u>>a[i].v; if(a[i].u>a[i].v) swap(a[i].u,a[i].v); ++d[a[i].u],++d[a[i].v]; } sort(a,a+m,cmp); for(int i =0;i<m;i++) { int u =a[i].u,v=a[i].v; if(fi(u)!=fi(v)) { cout<<u<<" "<<v<<endl; un(u,v); } } return 0; }