Spanning Tree with Maximum Degree

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct vv{
    int from,to;
};
int vis[N];//不能走到重复点.
vector<int>v[N];
vector<vv>ans;
int deg[N];//度

queue<int>q;

void bfs()
{
    while(q.size())
    {
        int temp=q.front();
        vis[temp]=1;
        q.pop();
        for(int i=0;i<v[temp].size();i++)
        {
            int x=v[temp][i];
            if(vis[x])  continue;
            vis[x]=1;
            ans.push_back({temp,x});
            q.push(x);
        }
    }
}

int main()
{
    int n,m,mx1=0,mx2=0;//mx1记录最大度数 mx2记录最大度数所在的点.
    scanf("%d%d",&n,&m);//点数 边数
    for(int i=0;i<m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
        deg[x]++;deg[y]++;
        if(deg[x]>mx1) {mx2=x;mx1=deg[x];}
        if(deg[y]>mx1) {mx2=y;mx1=deg[y];}
    }
    //找到了度数最大的点,然后进行删边.
    q.push(mx2);
    bfs();
    for(int i=0;i<ans.size();i++)
    {
        printf("%d %d\n",ans[i].from,ans[i].to);
    }
    return 0;
}

2333我感觉我应该学图论,感觉自己图论越来越好了,虽然也是个水题Hhhh
统计下度数最大的点作为顶点然后bfs成树即可.