链接：
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=1661
原题：
Graph is a collection of edges E and vertices V. Graph has a wide variety of applications in computer. There are different ways to represent graph in computer. It can be represented by adjacency matrix or by adjacency list. There are some other ways to represent graph. One of them is to write the degrees (the numbers of edges that a vertex has) of each vertex. If there are n vertices then n integers can represent that graph. In this problem we are talking about simple graph which does not have same endpoints for more than one edge, and also does not have edges with the same endpoint.
Any graph can be represented by n number of integers. But the reverse is not always true. If you are given n integers, you have to find out whether this n numbers can represent the degrees of n vertices of a graph.
Input
Each line will start with the number n (≤ 10000). The next n integers will represent the degrees of n vertices of the graph. A 0 input for n will indicate end of input which should not be processed.
Output
If the n integers can represent a graph then print “Possible”. Otherwise print “Not possible”. Output for each test case should be on separate line.
样例输入：
4 3 3 3 3
6 2 4 5 5 2 1
5 3 2 3 2 1
0
样例输出：
Possible
Not possible
Not possible
题目大意：
给出一张有n个点的图，然后再给出每个点的度数。求这个图是否可能存在。
更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/
分析与总结：
也是赤裸裸的Havel-Hakimi定理的应用。
代码：
/*
* UVa: 10720 - Graph Construction
* 贪心，Havel-Hakimi定理
* Time: 0.040s
* Author: D_Double
*
*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 10005
using namespace std;
int arr[MAXN],n;
bool Havel_Hakimi(){
for(int i=0; i<n-1; ++i){
sort(arr+i,arr+n,greater<int>());
if(i+arr[i] >= n) return false;
for(int j=i+1; j<=i+arr[i]; ++j){
--arr[j];
if(arr[j] < 0) return false;
}
}
if(arr[n-1]!=0) return false;
return true;
}
int main(){
while(scanf("%d",&n)&&n){
int sum=0;
bool flag=true;
for(int i=0; i<n; ++i){
scanf("%d",&arr[i]);
if(arr[i]>n-1) flag=false;
sum += arr[i];
}
if(sum%2!=0) flag=false;
if(sum==0 || flag&&Havel_Hakimi()) printf("Possible\n");
else printf("Not possible\n");
}
return 0;
}
作者：csdn博客 shuangde800
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索graph
， of
， The
construct
construction、construction bank、construction paper、fuzor construction、under construction，以便于您获取更多的相关知识。