给定一个非负整数序列{dn}，若存在一个无向图使得图中各点的度与此序列一一对应，则称此序列可图化。进一步，若图为简单图，则称此序列可简单图化。

此题因为是无自环无重边，所以是简单图。用判定简单图可图化的Havel-Hakimi定理。

Havel-Hakimi定理：

一个度序列：

是简单图度序列当且仅当：

是简单图的度序列。

简单来讲，算法流程如下：

设度序列为d1,d2,d3....dn

1.如果度序列中元素有负数或者度序列和不为偶数，则肯定不可图。

2.每次取度序列中最大元素，设为M,如果M>n-1（n为此时的元素数），则不可图。否则取次大的M个元素，将他们都减1，再次加入到度序列中，元素数减1，如此往复，直到：

（1）度序列出现负数元素，则不可图，退出。

（2）度序列全为0，则可图，退出。

 

回到题目，这题由于n过大（10^5），所以不能每次都排序来找前M大的数，所以考虑用优先队列来实现高效的插入，排序，取最大元素等操作。

（优先队列的复杂度）

代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              using namespace std;#define N 100007priority_queue
              
               
                ,less
                
                  > que;queue
                 
                   tmp;int check(int n){ int dmax,k,i; while(1) { dmax = que.top(); que.pop(); if(dmax > n-1) return 0; while(dmax--) { k = que.top(); que.pop(); k--; if(k < 0) return 0; tmp.push(k); } while(!tmp.empty()) { k = tmp.front(); tmp.pop(); que.push(k); } dmax = que.top(); if(dmax == 0 || n == 1) break; n--; } return 1;}int main(){ int t,n,i,x; scanf("%d",&t); while(t--) { while(!que.empty()) que.pop(); while(!tmp.empty()) tmp.pop(); scanf("%d",&n); int flag = 1; int sum = 0; for(i=0;i