首页 > ACM题库 > HDU-杭电 > hdu 2454 Degree Sequence of Graph G-拓扑排序-[解题报告]C++
2014
01-26

hdu 2454 Degree Sequence of Graph G-拓扑排序-[解题报告]C++

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?

输入:

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.

输出:

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.

样例输入:

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

样例输出:

yes
no

**======================================================**
题意:
给你一个图的每个点的度的序列问你能否把这个图建成一个简单图
分析:
定理引入:
Havel定理:给定一个非负整数序列{dn},若存在一个无
向图使得图中各点的度与此序列一一对应,则称此序列可图化。进
一步,若图为简单图,则称此序列可简单图化
可图化的判定:d1+d2+……dn=0(mod 2)。关于具体图的构造,我们
可以简单地把奇数度的点配对,剩下的全部搞成自环。   可简单
图化的判定(Havel定理):把序列排成不增序,即d1>=d2>=……>=dn,

则d可简单图化当且仅当d’={d2-1,d3-1,……d(d1+1)-1, d(d1+2),
d(d1+3),……dn}可简单图化。简单的说,把d排序后,找出度最大的
点(设度为d1),把它与度次大的d1个点之间连边,然后这个点就
可以不管了,一直继续这个过程,直到建出完整的图,或出现负度
等明显不合理的情况。
1 Havel定理:把度排序,从大到小,类似拓扑排序,只是把过程反
过来而已。
具体过程:
贪心的方法是每次把顶点按度大小从大到小排序,取出度最大的点
Vi,依次和度较大的那些顶点Vj连接,同时减去Vj的度。连接完之
后就不再考虑Vi了,剩下的点再次排序然后找度最大的去连接……这
样就可以构造出一个可行解。判断无解有两个地方,若某次选出的
Vi的度比剩下的顶点还多,则无解;若某次Vj的度减成了负数,则
无解。
2 定理1:总的度mod 2=0。
3 定理2:最大度<=n-1。
**======================================================**

#include<cstdio>
#include<algorithm>

using namespace std;

int a[1005];

bool cmp(int x , int y)
{
 return x>y;
}

int main()
{
 int t;
 scanf(“%d” , &t);
 while(t–)
 {
  int n ;
  scanf(“%d” ,
&n);
  int sum = 0;
  for(int i = 0 ; i
< n ; i++)
  {
   scanf(“%d” ,
&a[i]);
   sum +=
a[i];
  }

  if(sum%2)
  {
   printf(“no\n”);

   continue;

  }

  int f = 0;
  for(int i = 0 ; i
< n ; i++)
  {
   sort(a , a +
n , cmp);
   if(a[0] ==
0)
   {
    f
= 1;
    break;

   }

   for(int j
= 0 ; j < a[0] ; j++)
   {
    a[j+1]–;

    if(a[j+1]
< 0)
    {

     f
= 2;
     break;

    }

   }
   a[0] =
0;
   if(f == 2)
break;
  }

  if(f == 1)
printf(“yes\n”);
  else printf(“no\n”);

 }
 return 0;
}


解题转自:http://blog.sina.com.cn/s/blog_a3aa8cc401019zi1.html


  1. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。