CF 1133F1 - Spanning Tree with Maximum Degree

Rating: 1600
Tags: graphs
Solve time: 1m 58s
Verified: no

Solution

Problem Understanding

We are given a connected undirected graph and must select exactly $n-1$ of its edges so that they form a spanning tree.

Among all possible spanning trees, we want one whose largest vertex degree is as large as possible.

A spanning tree connects all vertices without cycles. The degree of a vertex inside the spanning tree is the number of chosen tree edges incident to it. Our goal is not to minimize or balance degrees, but to make the maximum degree achieved by some vertex as large as possible.

The graph contains up to $2 \cdot 10^5$ vertices and edges. These limits immediately rule out any approach that examines many spanning trees or performs expensive graph searches from every vertex. Since both $n$ and $m$ are around $200000$, an $O(n+m)$ or $O((n+m)\log n)$ solution is expected. Anything quadratic would be far too slow.

The most dangerous part of the problem is understanding what the optimal maximum degree actually is.

Consider a graph where vertex 1 is connected to every other vertex:

1-2
1-3
1-4
1-5

The spanning tree can simply use all four edges, giving vertex 1 degree 4. No other spanning tree can do better because vertex 1 only has four incident edges.

A different pitfall appears when a high-degree vertex participates in cycles:

1-2
1-3
1-4
2-3
3-4

A careless algorithm might try to include all edges adjacent to vertex 3, but spanning trees cannot contain cycles. The challenge is to include as many edges adjacent to one vertex as possible while still producing a valid tree.

Another subtle case is when several vertices share the same maximum degree:

1-2
1-3
2-4
3-4

Both vertices 1 and 4 have degree 2. Any optimal answer is acceptable. The algorithm must not depend on the maximizing vertex being unique.

Approaches

A brute-force mindset would start by asking: for every spanning tree of the graph, what is its maximum degree?

That idea is correct but hopelessly expensive. A graph can contain an exponential number of spanning trees. Even for moderate values of $n$, enumerating all of them is impossible.

The next idea is to focus on the vertex that might achieve the maximum degree.

Suppose we choose a vertex $v$. How many edges incident to $v$ can appear in a spanning tree?

A key observation is that every edge adjacent to $v$ can be included simultaneously.

Why? If we remove $v$ from the graph, the remaining vertices split into several connected components. Let that number be $k$.

To connect the whole graph into a tree, vertex $v$ must connect to every one of those components at least once. After that, inside each component we only need a spanning tree.

The number of edges from $v$ that can be used becomes:

$$\deg(v) - (k-1)$$

But in F1 there is an even simpler observation.

Let $r$ be a vertex of maximum degree in the original graph.

No spanning tree can give any vertex degree larger than its original graph degree. Since $r$ already has the largest graph degree, the maximum achievable tree degree cannot exceed $\deg(r)$.

Can we actually build a spanning tree where $r$ has degree exactly $\deg(r)$?

Yes.

Start a DFS or BFS from $r$. Whenever we discover an unvisited neighbor, add that edge to the answer. Since all neighbors of $r$ are discovered directly from $r$, every edge incident to $r$ gets included. The traversal then continues through the remaining graph.

The resulting structure is a spanning tree, and vertex $r$ has degree exactly equal to its original graph degree.

Since no tree degree can exceed the original graph degree of any vertex, this is optimal.

This transforms the problem into a very simple graph traversal.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force Enumeration of Spanning Trees	Exponential	Exponential	Too slow
DFS/BFS from Maximum-Degree Vertex	O(n + m)	O(n + m)	Accepted

Algorithm Walkthrough

Read the graph and build an adjacency list.
Compute the degree of every vertex.
Find a vertex $r$ with maximum degree in the original graph.
Start a DFS from $r$.
Whenever DFS traverses an edge $(u,v)$ to an unvisited vertex $v$, record that edge in the answer and mark $v$ visited.
Continue until all reachable vertices are visited.
Since the graph is connected, DFS visits every vertex exactly once.
Output all recorded edges.

Why it works

The DFS tree is always a spanning tree because every vertex except the root is reached through exactly one recorded edge, and DFS never adds an edge leading to an already visited vertex. Thus the result is connected and acyclic.

Let $r$ be a vertex with maximum graph degree. Every neighbor of $r$ is initially unvisited when DFS begins. When DFS processes $r$, it adds an edge from $r$ to every neighbor. Consequently, the degree of $r$ inside the DFS tree equals its original graph degree.

No spanning tree can give any vertex degree larger than its degree in the original graph. Since $r$ already has maximum graph degree, the spanning tree produced by DFS attains the largest possible maximum degree.

Python Solution

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

adj = [[] for _ in range(n + 1)]
deg = [0] * (n + 1)

for _ in range(m):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)
    deg[u] += 1
    deg[v] += 1

root = max(range(1, n + 1), key=lambda x: deg[x])

visited = [False] * (n + 1)
visited[root] = True

answer = []

stack = [root]

while stack:
    u = stack.pop()

    for v in adj[u]:
        if not visited[v]:
            visited[v] = True
            answer.append((u, v))
            stack.append(v)

sys.stdout.write("\n".join(f"{u} {v}" for u, v in answer))

The first part constructs the adjacency list and counts degrees simultaneously.

The choice of root is the central idea. We select any vertex whose graph degree is maximum. The correctness proof depends on starting the traversal from this vertex.

The DFS is implemented iteratively to avoid Python recursion depth issues. With up to 200000 vertices, recursive DFS could overflow the call stack.

A vertex is marked visited immediately when discovered, not when popped from the stack. This prevents multiple parents from recording duplicate tree edges to the same vertex.

Each recorded edge corresponds exactly to the moment a new vertex is discovered. Since every non-root vertex is discovered once, exactly $n-1$ edges are stored.

Worked Examples

Example 1

Input:

Degrees:

Vertex	Degree
1	2
2	2
3	3
4	1
5	2

Root = 3.

Step	Current Vertex	New Edge Added	Stack After Step
Start	-	-	[3]
1	3	(3,2)	[2]
1	3	(3,5)	[2,5]
1	3	(3,4)	[2,5,4]
2	4	-	[2,5]
3	5	(5,1)	[2,1]
4	1	-	[2]
5	2	-	[]

Produced tree:

Vertex 3 has degree 3, equal to its graph degree. Since no vertex in the graph has degree greater than 3, this is optimal.

Example 2

Input:

Root = 1.

Step	Current Vertex	New Edge Added	Stack After Step
Start	-	-	[1]
1	1	(1,2)	[2]
1	1	(1,3)	[2,3]
1	1	(1,4)	[2,3,4]
2	4	-	[2,3]
3	3	-	[2]
4	2	-	[]

Resulting tree:

1 2
1 3
1 4

The root keeps all three of its incident edges, achieving the largest possible degree.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	One pass to build the graph and one DFS traversal
Space	O(n + m)	Adjacency list, visited array, stack, and answer edges

The graph contains at most 200000 vertices and 200000 edges. Linear complexity easily fits within the limits. The memory usage is also comfortably below the 256 MB limit.

Test Cases

# helper validation routines for this problem

from collections import deque

def validate(n, edges, output):
    lines = [line.strip() for line in output.strip().splitlines() if line.strip()]
    assert len(lines) == n - 1

    graph_edges = set()
    for u, v in edges:
        graph_edges.add((min(u, v), max(u, v)))

    parent = list(range(n + 1))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(a, b):
        a = find(a)
        b = find(b)
        if a == b:
            return False
        parent[a] = b
        return True

    deg = [0] * (n + 1)

    for line in lines:
        u, v = map(int, line.split())

        assert (min(u, v), max(u, v)) in graph_edges
        assert union(u, v)

        deg[u] += 1
        deg[v] += 1

    roots = {find(i) for i in range(1, n + 1)}
    assert len(roots) == 1

# minimum graph
n = 2
edges = [(1, 2)]

# path graph
n = 4
edges = [(1, 2), (2, 3), (3, 4)]

# star graph
n = 5
edges = [(1, 2), (1, 3), (1, 4), (1, 5)]

# dense graph
n = 4
edges = [
    (1, 2),
    (1, 3),
    (1, 4),
    (2, 3),
    (2, 4),
    (3, 4)
]

# cycle graph
n = 5
edges = [
    (1, 2),
    (2, 3),
    (3, 4),
    (4, 5),
    (5, 1)
]

Because the output is not unique, validation must check structural correctness rather than exact edge order.

Test input	Expected output	What it validates
Single edge graph	Any valid tree	Minimum size
Path graph	Same path	DFS on sparse graph
Star graph	Center connected to all leaves	Maximum degree already obvious
Complete graph on 4 vertices	Any valid tree	Dense graph handling
Cycle graph	Any spanning tree	Cycle elimination

Edge Cases

Maximum-degree vertex is not unique

Input:

Vertices 1 and 4 both have degree 2. The algorithm may choose either one as root.

If root = 1, DFS immediately adds edges (1,2) and (1,3). The remaining vertex is reached through one additional edge. Vertex 1 keeps degree 2, which is optimal.

Graph already forms a tree

Input:

DFS simply reproduces the original tree. Since there are no extra edges, every spanning tree is identical to the input graph.

High-degree vertex inside many cycles

Input:

Vertex 1 has degree 4.

When DFS starts from 1, all four neighbors are unvisited, so all four edges incident to 1 enter the spanning tree immediately. Later cycle edges are ignored because their endpoints are already visited.

The resulting tree gives vertex 1 degree 4, matching its graph degree and achieving the optimum possible maximum degree.