F1. Spanning Tree with Maximum Degree

清疚 2022-03-11 16:56 140阅读 0赞

### 题目描述： ###

You are given an undirected unweighted connected graph consisting of nn vertices and mm edges. It is guaranteed that there are no self-loops or multiple edges in the given graph.

Your task is to find any spanning tree of this graph such that the maximum degree over all vertices is maximum possible. Recall that the degree of a vertex is the number of edges incident to it.

Input  
The first line contains two integers nn and mm (2≤n≤2⋅1052≤n≤2⋅105, n−1≤m≤min(2⋅105,n(n−1)2)n−1≤m≤min(2⋅105,n(n−1)2)) — the number of vertices and edges, respectively.

The following mm lines denote edges: edge ii is represented by a pair of integers vivi, uiui (1≤vi,ui≤n1≤vi,ui≤n, ui≠viui≠vi), which are the indices of vertices connected by the edge. There are no loops or multiple edges in the given graph, i. e. for each pair (vi,uivi,ui) there are no other pairs (vi,uivi,ui) or (ui,viui,vi) in the list of edges, and for each pair (vi,ui)(vi,ui) the condition vi≠uivi≠ui is satisfied.

Output  
Print n−1n−1 lines describing the edges of a spanning tree such that the maximum degree over all vertices is maximum possible. Make sure that the edges of the printed spanning tree form some subset of the input edges (order doesn’t matter and edge (v,u)(v,u) is considered the same as the edge (u,v)(u,v)).

If there are multiple possible answers, print any of them.

Examples  
inputCopy  
5 5  
1 2  
2 3  
3 5  
4 3  
1 5  
outputCopy  
2 3  
2 1  
3 4  
3 5  
inputCopy  
4 6  
1 2  
1 3  
1 4  
2 3  
2 4  
3 4  
outputCopy  
2 1  
1 3  
1 4  
inputCopy  
8 9  
1 2  
2 3  
2 5  
1 6  
3 4  
6 5  
4 5  
2 7  
5 8  
outputCopy  
3 2  
6 1  
2 5  
2 1  
2 7  
5 8  
3 4

###### 题目链接：[http://codeforces.com/contest/1133/problem/F1][http_codeforces.com_contest_1133_problem_F1] ######

##### 题意： #####

给你一个无向图。问在最小生成树的同时，使得根结点的入度最大。

###### 分析： ######

这个题的话，使得根结点的入度最大，不就是使得根结点的出度最大吗。  
那么我们直接从入度最多的点开始开始建树就可以了呀。  
然后这个题是打印，最小生成树的的边，没有顺序之分，答案也不唯一。  
这样的话，就十分简单了呀。用一个dfs+ vis标记就直接过了呀。  
如果我能提前十分钟做这个题，我这个题就可以AC的。 啊啊啊。  
AC代码：

#include"stdio.h"
    #include"string.h"
    #include"vector"
    #include"algorithm"
       using namespace std;
    vector<int>Q[200001];
    int vis[200001];
    void dfs(int maxx)
    {
        for(int i=0;i<Q[maxx].size();i++)
        {
            if(vis[Q[maxx][i]]==0)
              {
                  printf("%d %d\n",maxx,Q[maxx][i]);
                  vis[Q[maxx][i]]=1;
                  dfs(Q[maxx][i]);
              }
        }
        return ;
    }
    int main()
    {
        int n,m;
        int in[200001];
        while(~scanf("%d%d",&n,&m))
        {
            memset(vis,0,sizeof(vis));
            memset(in,0,sizeof(in));
            for(int i=0;i<m;i++)
            {
                int a,b;
                scanf("%d%d",&a,&b);
                in[b]++;//无向图
                in[a]++;
                Q[a].push_back(b);
                Q[b].push_back(a);
            }
            int maxx=1;
            for(int i=2;i<=n;i++)
                if(in[maxx]<in[i])
                  maxx=i;
            vis[maxx]=1;
            for(int i=0;i<Q[maxx].size();i++)//把最多的出度的边打印出来。
            {
                printf("%d %d\n",maxx,Q[maxx][i]);
                vis[Q[maxx][i]]=1;//标记一下。
            }
            for(int i=0;i<Q[maxx].size();i++)//开始dfs
               dfs(Q[maxx][i]);
        }
    }

[http_codeforces.com_contest_1133_problem_F1]: http://codeforces.com/contest/1133/problem/F1