题解 | 小红的二分图构造

1.由于每条边连接U和V中的一个节点，因此U的度数和V的度数应该相等，并且为总度数和的一半，故先计算度数和，若为奇数，返回-1

2.将度数较大的节点分配到U中，这样为U中每个节点u分配V中的节点v时可以保证u的度数比v的度数达

3.对于U中的每个节点u，根据其度数，为其分配相应个数的v结点，若v结点不够分配，返回-1

4.最后构造出的边集合即为所求

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    // Write your code here
    function constructBipartiteGraph(n, degrees) {
        const total = degrees.reduce((sum, cur) => sum + cur, 0) // 计算所有度数之和
        // 结点分成两个集合，每条边都连接U和V的一个节点
        // 那么只需要将度数平分给U和V
        if(total % 2 === 1) {
            //度数总和为奇数，非法，因为一条边连接两个结点，度数必然为偶数
            return -1
        }
        const half = total / 2
        // 根据度数构造结点，并按照度数从大到小排序
        const nodes = degrees.map((degree, i) => {
            return {index: i + 1, degree}
        }).sort((a, b) => b.degree - a.degree)

        let sumU = 0 // U中度数的和
        const U = []
        const V = []
        for(const node of nodes) {
            if(sumU + node.degree <= half) {
                sumU += node.degree
                // 加入到U集合中
                U.push(node)
            } else {
                V.push(node)
            }
        }

        if(sumU !== half) {
            // 无法构造满足条件的二分图
            return -1
        }

        const edges = [] // 根据U、V集合，构造边集合
        for(const u of U) {
            for(let i = 0; i < u.degree; i++) {
                // 对于u结点的每个度数，为其分配一个v结点
                // 由于nodes是按照degree从小到大排序的，因此能保证u的度数大于v的度数
                if(V.length === 0) {
                    // 没有结点可以分配
                    return -1
                }
                const v = V[0]
                // 将u结点的下标和v结点的下标加入到边集合中
                edges.push([u.index, v.index])
                v.degree--
                if(v.degree === 0) {
                    // v结点的度数用完了，将其中V集合中剔除
                    V.shift()
                }
            }
        }

        return {
            m: edges.length, // 边的数量
            edges
        }
    }
    while ((line = await readline())) {
        const m = +line;
        const degrees = (await readline()).split(" ").map(Number);
        const result = constructBipartiteGraph(m, degrees);
        if (result === -1) {
            console.log(-1);
        } else {
            console.log(result.m);
            result.edges.forEach((edge) => console.log(edge.join(" ")));
        }
    }
})();