Havel-Hakimi定理 hdu2454 / poj1695 Havel-Hakimi定理

Havel-Hakimi定理 hdu2454 / poj1695 Havel-Hakimi定理

Havel-Hakimi定理

當年一度熱門出現在ACM賽場上的算法。

算法定義：

Havel-Hakimi定理主要用來判定一個給定的序列是否是可圖的。

2，首先介紹一下度序列：若把圖 G 所有頂點的度數排成一個序列 S，則稱 S 為圖 G 的度序列。

3，一個非負整數組成的有限序列如果是某個無向圖的序列，則稱該序列是可圖的。

4，判定過程：（1）對當前數列排序，使其呈遞減，（2）從S【2】開始對其後S【1】個數字-1，（3）一直循環直到當前序列出現負數（即不是可圖的情況）或者當前序列全為0 （可圖）時退出。

5，舉例：序列S：7,7,4,3,3,3,2,1 刪除序列S的首項 7 ，對其後的7項每項減1，得到：6,3,2,2,2,1,0，繼續刪除序列的首項6，對其後的6項每項減1，得到：2,1,1,1,0，-1，到這一步出現了負數，因此該序列是不可圖的。

有2種不合理的情況：

（1）某次對剩下序列排序後，最大的度數（設為d1）超過了剩下的頂點數；

（2）對最大度數後面的d1個數各減1後，出現了負數。

兩道模板題：HDU2454（純裸題） / poj 1695(稍微改一下就好了)

模板：

struct Node{
   int id,num;
   bool operator < (const Node& rhs) const {
        if(num == rhs.num)
            return id < rhs.id;
        return num > rhs.num;
   }
}node[MAXN];
int n;
int mp[MAXN][MAXN];

void solve() {
   int sum = 0;
   for(int i = 0;i < n;++i)
      sum += node[i].num;

   if(sum & 1) {
        puts("NO");
        return;
   }

   int flag = 0;
   memset(mp,0,sizeof(mp));

   for(int i = 0;i < n;++i) {
      sort(node,node + n);

      if(0 == node[0].num) {
          flag = 1;
          break;
      }

      for(int j = 0;j < node[0].num;++j) {
          if(--node[j+1].num < 0) {
             flag = 2;
             break;
          }
          mp[node[0].id][node[j+1].id] = mp[node[j+1].id][node[0].id] = 1;
      }
      node[0].num = 0;
      if(flag == 2) break;
   }

   if(flag == 1) {
       puts("YES");
       for(int i = 0;i < n;++i)
         for(int j = 0;j < n;++j)
            printf("%d%c",mp[i][j],j==n-1?'\n':' ');
   } else {
       puts("NO");
   }
}