---
title: "AtCoder Beginner Contest 239 F(生成樹)"
tags: 題解, 資料結構, 並查集, 圖論, 生成樹
---

https://atcoder.jp/contests/abc239/tasks/abc239_f

#### 題意

給一個 $N$ 個點的圖，已經建好 $M$ 條邊，並給出數列 $D$，要求再新增 $N - M - 1$ 條邊使整張圖連通，且第 $i$ 個點的 degree 須為 $D[i]$。

#### 思路

由於 $M$ 條邊再加上 $N - M - 1$ 條邊形成 $N - 1$ 條邊，又要求須為連通圖，明顯看出要讓圖變成一棵生成樹。

首先我們可以把已經連通的塊收集起來 (Union Find)，根據塊中的點計算出整個塊所需新增的邊之數量，接下來就可以開始新增邊。

新增邊時只會在不同連通塊之間新增，且為了不讓某些塊無法與其他人連接，我們優先考慮那些需求為 $1$ 的連通塊，將其與剩下的塊中需求大於 $1$ 的塊相連 (若不存在則選擇需求為 $1$ 的塊也行)。如果發現連通的過程中塊數不足 $2$，或是不存在需求為 $1$ 的塊，則不可能完成生成樹。

#### Code

def solve():
    N, M = map(int, input().split())
    D = list(map(int, input().split()))

    if sum(D) != 2 * N - 2:
        print(-1)
        return

    dsu = DSU(N)
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1; b -= 1
        D[a] -= 1; D[b] -= 1
        if not dsu.union(a, b) or D[a] < 0 or D[b] < 0:
            print(-1)
            return

    deq = deque()
    for (_, grp) in dsu.all_groups().items():
        tot_need = 0
        needs = []
        for node in grp:
            if D[node]:
                tot_need += D[node]
                needs.append([node, D[node]])
        if tot_need > 1:
            deq.append([tot_need, needs])
        elif tot_need == 1:
            deq.appendleft([tot_need, needs])

    ans = []
    for _ in range(N - M - 1):
        if len(deq) < 2 or deq[0][0] != 1:
            print(-1)
            return
        grp1 = deq.popleft()
        grp2 = deq.pop()
        ans.append(str(grp1[1][-1][0] + 1) + " " + str(grp2[1][-1][0] + 1))
        for grp in (grp1, grp2):
            if grp[1][-1][1] == 1:
                grp[1].pop()
            else:
                grp[1][-1][1] -= 1
            grp[0] -= 1
            if grp[0] > 1:
                deq.append(grp)
            elif grp[0] == 1:
                deq.appendleft(grp)
    print(*ans, sep="\n")

if __name__ == "__main__":
    solve()