ACM | Degree Sequence of Graph G

Wang Haiyang is a strong and optimistic Chinese youngster. Although born and brought up in the northern inland city Harbin, he has deep love and yearns for the boundless oceans. After graduation, he came to a coastal city and got a job in a marine transportation company. There, he held a position as a navigator in a freighter and began his new life.

The cargo vessel, Wang Haiyang worked on, sails among 6 ports between which exist 9 routes. At the first sight of his navigation chart, the 6 ports and 9 routes on it reminded him of Graph Theory that he studied in class at university. In the way that Leonhard Euler solved The Seven Bridges of Knoigsberg, Wang Haiyang regarded the navigation chart as a graph of Graph Theory. He considered the 6 ports as 6 nodes and 9 routes as 9 edges of the graph. The graph is illustrated as below.

According to Graph Theory, the number of edges related to a node is defined as Degree number of this node.

Wang Haiyang looked at the graph and thought, If arranged, the Degree numbers of all nodes of graph G can form such a sequence: 4, 4, 3,3,2,2, which is called the degree sequence of the graph. Of course, the degree sequence of any simple graph (according to Graph Theory, a graph without any parallel edge or ring is a simple graph) is a non-negative integer sequence?

Wang Haiyang is a thoughtful person and tends to think deeply over any scientific problem that grabs his interest. So as usual, he also gave this problem further thought, As we know, any a simple graph always corresponds with a non-negative integer sequence. But whether a non-negative integer sequence always corresponds with the degree sequence of a simple graph? That is, if given a non-negative integer sequence, are we sure that we can draw a simple graph according to it.?

Let's put forward such a definition: provided that a non-negative integer sequence is the degree sequence of a graph without any parallel edge or ring, that is, a simple graph, the sequence is draw-possible, otherwise, non-draw-possible. Now the problem faced with Wang Haiyang is how to test whether a non-negative integer sequence is draw-possible or not. Since Wang Haiyang hasn't studied Algorithm Design course, it is difficult for him to solve such a problem. Can you help him?

王海洋是一位坚强、乐观的中国年轻人。 虽然出生和长大在北方内陆城市哈尔滨，但他对无边的海洋有着深深的热爱和向往。 毕业后，他来到沿海城市，在一家海运公司找到了工作。 在那里，他担任了一艘货轮的领航员，开始了他的新生活。

王海洋所在的货轮航行于6个港口，间有9条航线。 第一眼看到海图，上面的6个港口、9条航线让他想起了大学课堂上学过的图论。 就像欧拉求解克诺斯堡七桥一样，王海洋将航海图视为图论的图。 他将 6 个港口视为图的 6 个节点，将 9 条路线视为图的 9 条边。 图表如下图所示。

根据图论，与一个节点相关的边的数量被定义为该节点的度数。

王海洋看着图想，如果排列一下，图G所有节点的度数可以组成这样一个序列：4,4,3,3,2,2，称为图的度序列。 当然，任何简单图的度序列（根据图论，没有任何平行边或环的图就是简单图）是非负整数序列吗？

王海洋是一个有思想的人，凡是他感兴趣的科学问题都会深入思考。 所以像往常一样，他也对这个问题进行了进一步的思考，我们知道，任何一个简单的图总是对应着一个非负整数序列。 但非负整数序列是否总是对应于简单图的度序列呢？ 也就是说，如果给定一个非负整数序列，我们确定可以根据它画出一个简单的图吗？

我们提出这样一个定义：如果一个非负整数序列是一个没有任何平行边或环的图的度序列，即一个简单的图，则该序列是可绘制的，否则是不可绘制的 。 现在王海洋面临的问题是如何测试一个非负整数序列是否可以抽奖。 由于王海洋没有学过算法设计课程，所以他很难解决这样的问题。 你能帮助他吗？

ChatGPT给出的参考： 图论中的"简单图"是指一种特殊类型的图，具有以下特点： 无重复边：简单图中不存在重复的边，即每两个顶点之间最多有一条边。 无自环：简单图中不存在自环，即没有一条连接一个顶点到自己的边。 无向图：简单图是无向图，其中的边没有方向，即边的两个端点之间没有箭头或方向。 无权图：简单图通常是无权图，也就是说，边没有与之相关联的权重或数值。

输入格式:

The first line of input contains an integer T, indicates the number of test cases. In each case, there are n+1 numbers; first is an integer n (n<1000), which indicates there are n integers in the sequence; then follow n integers, which indicate the numbers of the degree sequence. 输入的第一行包含一个整数T，表示测试用例的数量。 在每种情况下，都有 n+1 个数字； 第一个是整数n（n<1000），表示序列中有n个整数； 接下来是n个整数，表示度数序列的个数。

输出格式:

For each case, the answer should be "yes"or "no" indicating this case is "draw-possible" or "non-draw-possible" 对于每种情况，答案应该是“yes”或“no”，表明这种情况是“可以绘画”或“不可以绘画”

输入样例:

2
6 4 4 3 3 2 2
4 2 1 1 1

输出样例:

yes
no

代码示例：

#include<stdio.h>
#include<stdlib.h>
int compare(const void *a,const void *b){
    return -(*(int*)a - *(int*)b);
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int N;
        scanf("%d",&N);
        int degree[1000];
        for(int i=0;i<N;i++){
            scanf("%d",degree+i);
        }
        int flag=1;
        qsort(degree,N,sizeof(int),compare);
        while(degree[0]>0 && flag==1){
            if(degree[0]<0 || degree[0]>N-1){
                printf("no\n");
                flag=0;
            }
            if(degree[0]==0){
                printf("yes\n");
                flag=0;
            }
            for(int i=1;i<=degree[0];i++){
                degree[i]--;
            }
            degree[0]=0;
            qsort(degree,N,sizeof(int),compare);
            if(degree[N-1]<0){
                printf("no\n");
                flag=0;
            }
        }
        if(flag==1){
            printf("yes\n");
        }
    }
    return 0;
}