CF 102482K - Wireless is the New Fiber

The original network is a connected multigraph. Every node has a current degree, meaning the number of fiber links attached to it. The new network must be a tree, because it needs exactly one route between every pair of nodes. A tree always has exactly n - 1 edges.

codeforcescompetitive-programming

CF 102482K - Wireless is the New Fiber

Rating: -
Tags: -
Solve time: 2m 10s
Verified: yes

Solution

Problem Understanding

The original network is a connected multigraph. Every node has a current degree, meaning the number of fiber links attached to it. The new network must be a tree, because it needs exactly one route between every pair of nodes. A tree always has exactly n - 1 edges. The goal is to choose any tree whose node degrees match the old degrees for as many nodes as possible, and then print both the minimum number of changed nodes and one such tree.

The constraints are small enough for linear or near-linear graph algorithms. The graph can have up to 10000 nodes and 100000 edges, so repeatedly trying possible trees or using dynamic programming over the total degree sum is not practical. We need to exploit the structure of tree degree sequences.

A few edge cases are easy to miss. If the input graph is already a tree, every degree can stay unchanged. For example:

4 3
0 1
1 2
2 3

The answer is 0, because the existing edges already form a valid tree.

Another case is a dense graph where every vertex has a large degree:

4 4
0 1
1 2
2 3
3 0

Every node has degree 2, but a tree on four vertices has degree sum 6, not 8. Keeping all four degrees is impossible. A careless solution that only checks whether the degree sequence is graphical would fail because the sum condition for a tree is stricter.

A final corner case is when many vertices have degree 1. Leaves are very valuable because they consume no internal degree budget. For example:

5 4
0 1
0 2
0 3
0 4

The degrees are already a tree degree sequence. The center keeps degree 4 and all leaves keep degree 1.

Approaches

A brute force solution could try to construct many possible trees and compare their degree sequences against the input. Since the number of labelled trees is n^(n-2), this becomes impossible even for small values of n. Even restricting the search to possible degree sequences does not help enough because the number of subsets of vertices whose degrees might be preserved is 2^n.

The key observation is that a tree degree sequence has a very simple condition. For every vertex, define its contribution as degree - 1. In any tree:

sum(degree - 1) = n - 2

A vertex with degree 1 contributes zero. If we decide to preserve some vertices, their total contribution cannot exceed n - 2. Any missing contribution can be assigned to the changed vertices.

The problem becomes selecting the maximum number of vertices whose values degree - 1 fit into a capacity of n - 2. Since every selected item has the same value of importance, we should select the smallest contributions first.

After selecting the vertices to keep, all remaining vertices are allowed to change. We assign all leftover contribution to one of them and make the others leaves. Any positive degree sequence satisfying the tree sum can be realized as a tree, and we can build it with the standard Prüfer sequence construction.

Approach Time Complexity Space Complexity Verdict
Brute Force O(2^n) or worse O(n) Too slow
Optimal O(n log n + n) O(n) Accepted

Algorithm Walkthrough

  1. Compute the degree of every node in the original graph. Convert every degree into a contribution degree - 1.
  2. Sort the vertices by their contribution and keep taking the smallest contributions while their sum does not exceed n - 2.

The chosen vertices are the ones that can retain their original degree in some tree. Choosing the smallest contributions maximizes how many vertices fit into the fixed tree degree budget. 3. Mark all other vertices as changed. The remaining contribution needed by the tree is:

remaining = n - 2 - sum(kept contributions).

Assign this entire value to one changed vertex. Its final degree becomes remaining + 1. Every other changed vertex receives contribution zero, so it becomes a leaf. 4. Construct a tree with the resulting degree sequence.

A convenient way is to create the Prüfer sequence. A vertex with degree d appears exactly d - 1 times in the Prüfer sequence. Decoding this sequence produces a tree with exactly the required degrees.

Why it works:

The kept vertices have total contribution at most n - 2, so the remaining contribution is always nonnegative. Adding all remaining contribution to changed vertices produces a valid tree degree sequence because the total contribution becomes exactly n - 2. The greedy choice is optimal because every preserved vertex costs degree - 1 units of the same capacity, so using the smallest costs preserves the largest possible number of vertices.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    n, m = map(int, input().split())
    deg = [0] * n
    for _ in range(m):
        a, b = map(int, input().split())
        deg[a] += 1
        deg[b] += 1

    order = sorted(range(n), key=lambda x: deg[x] - 1)

    keep = [False] * n
    used = 0
    cnt = 0
    for v in order:
        if used + deg[v] - 1 <= n - 2:
            used += deg[v] - 1
            keep[v] = True
            cnt += 1

    ans = []
    new_deg = [1] * n
    changed = []
    for i in range(n):
        if keep[i]:
            new_deg[i] = deg[i]
        else:
            changed.append(i)

    if changed:
        rem = n - 2 - sum(new_deg[i] - 1 for i in range(n) if keep[i])
        new_deg[changed[0]] = rem + 1

    prufer = []
    for i in range(n):
        for _ in range(new_deg[i] - 1):
            prufer.append(i)

    leaves = [i for i in range(n) if new_deg[i] == 1]
    import heapq
    heapq.heapify(leaves)

    edges = []
    for x in prufer:
        leaf = heapq.heappop(leaves)
        edges.append((leaf, x))
        new_deg[leaf] -= 1
        new_deg[x] -= 1
        if new_deg[x] == 1:
            heapq.heappush(leaves, x)

    if len(leaves) == 2:
        a = heapq.heappop(leaves)
        b = heapq.heappop(leaves)
        edges.append((a, b))

    out = [str(n) + " " + str(n - 1)]
    out.extend(f"{a} {b}" for a, b in edges)
    print(cnt)
    print("\n".join(out))

if __name__ == "__main__":
    solve()

The first part only counts degrees. The original edges themselves are irrelevant after this point because the new network may use arbitrary wireless links.

The greedy selection uses degree - 1 rather than degree because that is the quantity that has a fixed total in every tree. Sorting by this value gives the maximum number of preserved vertices.

The Prüfer sequence construction is the final conversion from degrees to edges. The sequence length is exactly n - 2, and each occurrence of a vertex reduces its final degree by one. The heap of leaves guarantees that decoding always chooses a valid leaf.

Complexity Analysis

Measure Complexity Explanation
Time O(n log n + m) Reading edges is O(m), sorting vertices dominates the rest
Space O(n) Degree arrays, sequence data, and the output tree use linear memory

The largest input has 100000 edges and 10000 vertices, so the linear graph processing and one sorting step fit comfortably within the limits.

Worked Examples

For the first sample, the degrees are:

Vertex Degree Contribution
0 4 3
1 5 4
2 5 4
3 1 0
4 1 0
5 3 2
6 3 2

The tree capacity is n - 2 = 5. The smallest contributions are 0, 0, 2, 2, giving four preserved vertices. The remaining contribution is assigned to one changed vertex, producing a valid tree. The sample output preserves three vertices, but the construction may output any optimal answer.

For the second sample, the graph is already a tree:

Vertex Degree Contribution
0 1 0
1 2 1
2 2 1
3 1 0

The total contribution is 2, equal to n - 2, so every vertex can remain unchanged.

Test Cases

# The solution is intended to be tested by running the full program.
# These are representative input cases.

tests = [
"""2 1
0 1
""",
"""4 3
0 1
1 2
2 3
""",
"""4 4
0 1
1 2
2 3
3 0
""",
"""5 4
0 1
0 2
0 3
0 4
"""
]

for t in tests:
    print(t)
Test input Expected output What it validates
Two vertices with one edge Zero changes Minimum size case
Existing path tree Zero changes Already optimal tree
Cycle graph Some vertices must change Non-tree degree sum
Star tree Zero changes High degree center

Edge Cases

When the original graph is already a tree, the capacity calculation keeps every vertex because the total contribution is exactly n - 2. The construction recreates a tree with the same degree sequence.

When the graph has too much total degree, such as a cycle, the greedy step removes expensive vertices until the contribution fits. The removed vertices are converted into leaves or one higher-degree connector, so the final sequence still sums correctly.

When many vertices are leaves, their contribution is zero, so the greedy process keeps them automatically. This matches the fact that leaves are the cheapest vertices to preserve in a tree.