题目背景

本题要求判断给定的非负整数序列是否为某简单无向图的度数序列（即可图性问题）。若可图，输出对应的邻接矩阵；否则输出"$NO$"。

算法思路：Havel-Hakimi算法

可图性问题的经典解法是Havel-Hakimi算法，核心步骤如下：

1. 将度数序列降序排列。
2. 取最大度数 $d$，将其后的 $d$ 个度数各减1（表示该节点与这 $d$ 个节点连边）。
3. 重复上述步骤，直到所有度数为0（可图）或出现负数/无法完成减操作（不可图）。

代码解释

以下是代码的关键逻辑说明：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <memory.h>

using namespace std;

const int maxn = 12;

// 存储节点ID和度数的结构体
class Pair {
public: 
    int m_id;  // 节点编号（1~n）
    int val;   // 节点度数
};

// 降序排序规则
bool cmp(Pair a, Pair b) {
    return a.val > b.val;
}

int main() {
    Pair p[maxn];       // 存储各节点的度数和ID
    int ans[maxn][maxn];// 邻接矩阵（ans[i][j]=1表示i和j有边）
    int T;              // 测试用例数
    scanf("%d", &T);
    while (T--) {
        int n;          // 节点数
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            p[i].m_id = i + 1;  // 节点ID从1开始
            scanf("%d", &p[i].val); // 读取度数
        }
        memset(ans, 0, sizeof(ans)); // 初始化邻接矩阵为0
        bool flag = true;  // 标记是否可图
        int num = n;       // 剩余处理次数（最多n次）
        
        while (num--) {
            sort(p, p + n, cmp);  // 按度数降序排序
            if (p[0].val == 0) break;  // 所有度数已处理完
            
            int d = p[0].val;  // 当前最大度数
            // 尝试连接后续d个节点
            for (int i = 1; i <= d; i++) {
                if (i < n && p[i].val > 0) {  // 确保节点存在且度数合法
                    // 标记边（无向图，双向记录）
                    ans[p[0].m_id][p[i].m_id] = 1;
                    ans[p[i].m_id][p[0].m_id] = 1;
                    p[i].val--;  // 被连接的节点度数减1
                } else {
                    flag = false;  // 无法连接，标记不可图
                    break;
                }
            }
            if (!flag) break;
            p[0].val = 0;  // 当前节点度数处理完毕，置0
        }
        
        if (flag) {
            puts("YES");
            // 输出邻接矩阵
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    printf(j == 1 ? "%d" : " %d", ans[i][j]);
                }
                putchar('\n');
            }
        } else {
            puts("NO");
        }
        if (T > 0) putchar('\n');  // 测试用例间换行
    }
    return 0;
}

关键步骤说明

1. 输入处理：读取测试用例数 $T$，每个用例读取节点数 $n$ 和各节点的度数。
2. 排序与处理：
   • 每次将度数序列降序排序，取最大度数 $d$。
   • 尝试将该节点与后续 $d$ 个节点连边（邻接矩阵标记为1），并将这些节点的度数减1。
   • 若后续节点不足 $d$ 个或某节点度数已为0（无法减1），则不可图。
3. 输出结果：若所有度数成功处理为0，输出邻接矩阵；否则输出"NO"。

复杂度分析

• 时间复杂度：每次测试用例的时间为 $O(n^2 \log n)$（排序的 $O(n \log n)$ 乘以最多$n$ 次循环）。
• 空间复杂度：$O(n^2)$（邻接矩阵存储）。