标题：给出顶点度数，图的存在性证明
出处：Felix021
时间：Sun, 08 Jun 2008 23:07:00 +0000
作者：felix021
地址：https://www.felix021.com/blog/read.php?969

内容：
WHUACM 20080608 Day4个人赛C题

描述：给出图的顶点数以及每个顶点的度数（每两个顶点之间最多只有一条边），证明该图的存在性。

证明：
将图的顶点按度数排序，找到度数最大的顶点（设度数为n0）
去掉这个顶点，同时使接下来n0个顶点的顶点数减一。
重复上述步骤，直至剩余顶点的度数都为0，则图存在，否则图不存在。

C代码:

#include<stdio.h>

int d[1010];
void qsort(int a[], int s, int e);

int main(){
    int n, i, j, sum;
    scanf("%d", &n);//输入顶点数
    sum = 0;
    for(i = 0; i < n; i++){
      scanf("%d", &d[i]);//输入每个顶点的度数
      sum += d[i];
    }
    if(sum % 2 == 1){ //如果总度数为奇数，就不存在
      printf("NO\n");
      return 0;
    }
    qsort(d, 0, n-1);//先排序 
    for(i = n - 1; i >= 0; i--){
      if(d[i] > i){ //如果最大度数大于剩余顶点数 就不存在
        printf("NO\n");
        return 0;
      }else{//否则去掉最大的顶点 
        for(j = 0; j < d[i]; j++){
          d[i-j-1]--;
          if(d[i-j-1] < 0){//如果出现负度数 就不存在
            printf("NO\n");
            return 0;
          }
        }
        qsort(d, 0, i - 1);//再次排序 
      }
    }
    printf("YES\n");//满足所有条件，存在
    return 0;
}

void qsort(int a[], int s, int e){
  int i = s, j = e, temp = a[s];
  if(s < e){
    while(i != j){
      while(a[j] > temp && i < j) j--;
      if(i < j) a[i++] = a[j];
      while(a[i] < temp && i < j) i++;
      if(i < j) a[j--] = a[i];
    }
    a[i] = temp;
    qsort(a, s, i-1);
    qsort(a, i+1, e);
  }
}



Generated by Bo-blog 2.1.0