codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1133F1.md (2991B)


      1 Source: https://codeforces.com/problemset/problem/1133/F1
      2 
      3 F1. Spanning Tree with Maximum Degree
      4 
      5 time limit per test
      6 
      7 3 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given an undirected unweighted connected graph consisting of $n$ vertices and $m$ edges. It is guaranteed that there are no self-loops or multiple edges in the given graph.
     22 
     23 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.
     24 
     25 Input
     26 
     27 The first line contains two integers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5$, $n - 1 \le m \le min(2 \cdot 10^5, \frac{n(n-1)}{2})$) — the number of vertices and edges, respectively.
     28 
     29 The following $m$ lines denote edges: edge $i$ is represented by a pair of integers $v_i$, $u_i$ ($1 \le v_i, u_i \le n$, $u_i \ne v_i$), 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 ($v_i, u_i$) there are no other pairs ($v_i, u_i$) or ($u_i, v_i$) in the list of edges, and for each pair $(v_i, u_i)$ the condition $v_i \ne u_i$ is satisfied.
     30 
     31 Output
     32 
     33 Print $n-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)$ is considered the same as the edge $(u, v)$).
     34 
     35 If there are multiple possible answers, print any of them.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 5 5
     43 1 2
     44 2 3
     45 3 5
     46 4 3
     47 1 5
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 3 5
     54 2 1
     55 3 2
     56 3 4
     57 ```
     58 
     59 Input
     60 
     61 ```
     62 4 6
     63 1 2
     64 1 3
     65 1 4
     66 2 3
     67 2 4
     68 3 4
     69 ```
     70 
     71 Output
     72 
     73 ```
     74 4 1
     75 1 2
     76 1 3
     77 ```
     78 
     79 Input
     80 
     81 ```
     82 8 9
     83 1 2
     84 2 3
     85 2 5
     86 1 6
     87 3 4
     88 6 5
     89 4 5
     90 2 7
     91 5 8
     92 ```
     93 
     94 Output
     95 
     96 ```
     97 3 2
     98 2 5
     99 8 5
    100 6 1
    101 2 7
    102 1 2
    103 3 4
    104 ```
    105 
    106 Note
    107 
    108 Picture corresponding to the first example: ![](https://espresso.codeforces.com/3a8d1688c0bdf10804012227ba99c68d627acd90.png)
    109 
    110 In this example the number of edges of spanning tree incident to the vertex $3$ is $3$. It is the maximum degree over all vertices of the spanning tree. It is easy to see that we cannot obtain a better answer.
    111 
    112 Picture corresponding to the second example: ![](https://espresso.codeforces.com/55d8d825e49b9d20df52c96228a19d220bcd963d.png)
    113 
    114 In this example the number of edges of spanning tree incident to the vertex $1$ is $3$. It is the maximum degree over all vertices of the spanning tree. It is easy to see that we cannot obtain a better answer.
    115 
    116 Picture corresponding to the third example: ![](https://espresso.codeforces.com/43278e43162c10f66d929244313dcafea9b624b4.png)
    117 
    118 In this example the number of edges of spanning tree incident to the vertex $2$ is $4$. It is the maximum degree over all vertices of the spanning tree. It is easy to see that we cannot obtain a better answer. But because this example is symmetric, we can choose almost the same spanning tree but with vertex $5$ instead of $2$.