admin管理员组文章数量:1602097
raph Construction | |
Time Limit | 2 Seconds |
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 nintegers, 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 nvertices 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.
Sample Input | Output for Sample Input |
4 3 3 3 3 | Possible |
A graphic sequence is a sequence of numbers which can be the degree sequence of some graph. A sequence can be checked to determine if it is graphic using GraphicQ[g] in the Mathematica package Combinatorica` .
Erdős and Gallai (1960) proved that a degree sequence is graphic iff the sum of vertex degrees is even and the sequence obeys the property
for each integer (Skiena 1990, p. 157), and this condition also generalizes to directed graphs. Tripathi and Vijay (2003) showed that this inequality need be checked only for as many as there are distinct terms in the sequence, not for all .
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,num[10010],sum[10010];
bool cmp(int a,int b){
return b<a;
}
int main(){
while(~scanf("%d",&n)&&n){
sum[0] = 0;
for(int i = 1; i <= n; i++){
scanf("%d",&num[i]);
}
sort(num+1,num+n+1,cmp);
for(int i = 1; i <= n; i++)
sum[i] = num[i]+sum[i-1];
if(sum[n]%2==0){
bool flag = 1;
for(int i = 1; i <= n; i++){
int k = i*(i-1);
if(k>=sum[i]) continue;
for(int j = i+1; j <= n; j++){
k += min(i,num[j]);
}
// cout<<k<<" "<<sum[i]<<" "<<i<<endl;
if(sum[i] > k){
flag = 0;
break;
}
}
if(flag)
cout<<"Possible"<<endl;
else
cout<<"Not possible"<<endl;
}else{
cout<<"Not possible"<<endl;
}
}
return 0;
}
本文标签: Graphconstruction
版权声明:本文标题:UVa10720 - Graph Construction 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1728397199a1157146.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论