最初の考え

ABC239_F

制約から、条件を満たす建設方法の完成形は必ず木になる。
頂点 1 つを基準として選んで、各頂点を順番に舐め、基準頂点に結合していない頂点を基準頂点に結合した頂点のグループに結合させればよさそう。
結合可能かを決める制約は各頂点から出ている辺の本数 D で与えられている。
制約 D が甘い、頂点から出ている辺の本数が多い頂点から順番に舐めていけば解けそう。

提出コード

提出したコードでは、 7WA でした。

提出コード

import sys
from collections import deque


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n  # 負値 :-size  正:parent を表す

    def find(self, x):  # root を返す
        if self.parents[x] < 0:
            return x
        else:
            return self.find(self.parents[x])

    def union(self, x, y):  # x, y を結合する
        x_root = self.find(x)
        y_root = self.find(y)

        if x_root == y_root:
            return

        if self.parents[x_root] > self.parents[y_root]:
            x_root, y_root = y_root, x_root

        self.parents[x_root] += self.parents[y_root]
        self.parents[y_root] = x_root

    def size(self, x):  # x が含まれる木のサイズを返す
        return -self.parents[self.find(x)]

    def same(self, x, y):  # x, y が同一の木に含まれるか返す
        return self.find(x) == self.find(y)

    def members(self, x):  # x を含む木に含まれるメンバーをかえす
        x_root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == x_root]

    def roots(self):  # 根の一覧を返す
        return [i for i in range(self.n) if self.parents[i] < 0]


def main():
    N, M = map(int, sys.stdin.readline().strip().split())
    D = list(map(int, sys.stdin.readline().strip().split()))

    uf = UnionFind(N)

    g = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, sys.stdin.readline().strip().split())
        a -= 1
        b -= 1

        g[a].append(b)
        g[b].append(a)

        # D は自由に書き足せる出ている辺の数
        D[a] -= 1
        D[b] -= 1

        uf.union(a, b)

    # そもそも無理
    for d in D:
        if d < 0:
            print(-1)
            return

    D = [(d, i) for i, d in enumerate(D)]
    D.sort()
    D.reverse()

    q = deque()  # 辺を書き足せる頂点
    for _ in range(D[0][0]):
        q.append(D[0][1])

    u = q[0]
    new_edge = []
    for d, v in D[1:]:

        if uf.same(u, v):
            for _ in range(d):
                q.append(v)
            continue

        # 結合する余裕がない
        if not q or d < 1:
            print(-1)
            return

        for _ in range(d - 1):
            q.append(v)

        uf.union(u, v)
        new_edge.append((q.popleft(), v))

    # 辺が余っている
    if q:
        print(-1)
        return

    for i, j in new_edge:
        print(i + 1, j + 1)

    return


if __name__ == "__main__":
    main()

提出コード間違い

コード中では、頂点から生やせる辺の余裕をキューで管理している。
例えば頂点 1 から辺を 3 本生やせるならばキューに 1, 1, 1 を入れる。
頂点の結合時はキューから辺を生やせる頂点を消費して辺を生やす。

WA 後に考察して気が付いたことは、結合可能な頂点を、辺を生やす余裕を持つ頂点として、一緒くたにまとめていることが問題だということです。
一緒くたにまとめる方法では、辺を生やす余裕が 1 の頂点について上手く処理できません。
具体的には、辺を生やす余裕が 1 であり既に他の頂点と結合済みの頂点は、グループ全体に辺を生やす余裕 1 を提供するのに対して、他の頂点と結合済みではない辺を生やす余裕が 1 の頂点は、自身の結合で辺を生やす余裕を使い切ってしまう。
つまり、辺を生やす余裕 1 の頂点はキューに余裕を足す頂点とキューから余裕を消費する頂点がある。
そして、余裕を消費する頂点が先に処理された場合は、辺を生やす余裕が残っていないために結合不可として解答してしまいます。
つまり、グループに余裕をもたらす頂点を先に処理しなければ WA となります。

というところまでは考察できましたが実装方法がよい思いつかず...

正解コード

AC コードはこちらです。 AC コード

データ構造をマージするテクにより、結合可能な頂点を管理することで実装しました。
ユーザー解説読んで、データ構造のマージを使えばできる事がわかりました。