题目链接:http://codeforces.com/contest/1133/problem/F1
题意是给了n个点m条无向边,让求一个生成树,使得每个点的度数尽量大。
思路就是我们按照点的度数去bfs跑一下就好了。
AC代码:
#include <bits/stdc++.h>
#define ll long long
#define maxn 200005
using namespace std;
int n,m;
vector<int> v[maxn];
int pos, cnt;
void bfs(){
queue<int> q;
bool vis[maxn];
memset(vis,false,sizeof(vis));
q.push(pos);
vis[pos] = true;
while(!q.empty()){
int u = q.front();
q.pop();
for(int i=0;i<v[u].size();i++){
if(vis[v[u][i]] == false){
vis[v[u][i]] = true;
printf("%d %d\n", u, v[u][i]);
q.push(v[u][i]);
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
cnt = 0;
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);
if(cnt < v[x].size()){
cnt = v[x].size();
pos = x;
}
if(cnt < v[y].size()){
cnt = v[y].size();
pos = y;
}
}
bfs();
return 0;
}