cf 1133 F1. Spanning Tree with Maximum Degree

n个点，m条边，没有边权，然后每次问你找出一颗生成树，使得其中的点的度数最大

只要随便找一个度数最大的点，然后与他相连的边用并查集瞎合并就可以，然后就是遍历一下其他遍，也合并一下即可

或者从度数最大的点开始bfs，形成一个“菊花图”（别问我，别人告诉我的，我从来不知道有这个东西）

代码:

#include <bits/stdc++.h>
#include <time.h>


using namespace std;

typedef long long ll;
typedef double db;
int xx[4] = {1,-1,0,0};
int yy[4] = {0,0,1,-1};
const double eps = 1e-9;
typedef pair<int,int>  P;
const int maxn = 2e6 + 5000;
const ll mod = 1e9 + 7;
inline int sign(db a) {
    return a < -eps ? -1 : a > eps;
}
inline int cmp(db a,db b) {
    return sign(a - b);
}
ll mul(ll a,ll b,ll c) {
    ll res = 1;
    while(b) {
        if(b & 1) res *= a,res %= c;
        a *= a,a %= c,b >>= 1;
    }
    return res;
}
ll phi(ll x) {
    ll res = x;
    for(ll i = 2; i * i <= x; i++) {
        if(x % i == 0) res = res / i * (i - 1);
        while(x % i == 0) x /= i;
    }
    if(x > 1) res = res / x  * (x - 1);
    return res;
}
int fa[maxn];
int Find(int x) {
    if(x != fa[x]) return fa[x] = Find(fa[x]);
    return fa[x];
}
ll c,n,k;
int a[maxn];
int b[maxn];
P p[maxn];
void unionn(int x,int y) {
    int X=Find(x);
    int fb=Find(y);
    if(X!=fb) fa[X]=fb;
}//将被边连接的两个独立集合合并
int m;
int vis[maxn];
int main() {
    ios::sync_with_stdio(false);
    while(cin >> n >> m) {
        memset(vis,0,sizeof(vis));
        for(int i = 1; i <= m; i++) {
            cin >> p[i].first >> p[i].second;
            vis[p[i].first]++;
            vis[p[i].second]++;
        }
        int Max = 0,id = 0;
        for(int i = 1;i <= n;i++){
            if(Max < vis[i]){
                Max = vis[i];
                id = i;
            }
        }
        vector<P>ans;
        int cnt = 0;
        for(int i=1; i<=n; i++) {
            fa[i]=i;
        }
        for(int i = 1;i <= m;i++){
            if(Find(p[i].first) != Find(p[i].second) && (id == p[i].first || id == p[i].second))
                unionn(p[i].first,p[i].second),cnt++,ans.push_back(p[i]),vis[i] = 1;
        }
        for(int i=1; i<=m; i++) {
            if(cnt==n-1) break;//当已经有n-1条边的时候，结束
            if(Find(p[i].first) != Find(p[i].second)) {
                unionn(p[i].first,p[i].second);
                cnt++;
                ans.push_back(p[i]);
            }
        }
//        cout << ans.size() << endl;
        for(auto d:ans) {
            cout << d.first << " " << d.second << endl;
        }
    }
    cerr << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
    return 0;
}