# HDU 4797-Graph Reconstruction[解题报告]HOJ

2016-03-14 15:06:30来源:[db:出处]作者:[db:作者]人点击

Graph Reconstruction

Time Limit:2 Seconds Memory Limit:65536 KB Special Judge

Let there be a simple graph withNvertices but we just know the degree of each vertex. Is it possible to reconstruct the graph only by these information?

A simple graph is an undirected graph that has no loops (edges connected at both ends to the same vertex) and no more than one edge between any two different vertices. The degree of a vertex is the number of edges that connect to it.

Input

There are multiple cases. Each case contains two lines. The first line contains one integerN(2 ≤N≤ 100), the number of vertices in the graph. The second line conrainsNintegers in which the ithitem is the degree of ithvertex and each degree is between 0 andN-1(inclusive).

Output

If the graph can be uniquely determined by the vertex degree information, output “UNIQUE” in the first line. Then output the graph.

If there are two or more different graphs can induce the same degree for all vertices, output “MULTIPLE” in the first line. Then output two different graphs in the following lines to proof.

If the vertex degree sequence cannot deduced any graph, just output “IMPOSSIBLE”.

The output format of graph is as follows:

N Eu

1

u

2

... u

E

v

1

v

2

... v

EWhereNis the number of vertices andEis the number of edges, and {ui,vi} is the ithedge the the graph. The order of edges and the order of vertices in the edge representation is not important since we would use special judge to verify your answer. The number of each vertex is labeled from 1 to N. See sample output for more detail.

Sample Input1065 5 5 4 4 365 4 4 4 4 363 4 3 1 2 0Sample OutputUNIQUE1 0UNIQUE6 133 3 3 3 3 2 2 2 2 1 1 1 52 1 5 4 6 1 5 4 6 5 4 6 4MULTIPLE6 121 1 1 1 1 5 5 5 6 6 2 25 4 3 2 6 4 3 2 4 3 4 36 121 1 1 1 1 5 5 5 6 6 3 35 4 3 2 6 4 3 2 4 2 4 2IMPOSSIBLE思路:这是一道坑题.......坑在格式的就不说了,可以原谅oj.如果hdu4797交不过,去zoj3732就能过了,(因为不能specail judge纯oj问题).#include #include #include using namespace std;const int maxn=111;int sum,n;typedef pair P;P deg[maxn];P tmpdeg[maxn];int ash1[maxn*maxn*2],ash2[maxn*maxn*2],alen;bool cmp(P A,P B){ if(A.first==B.first) return A.secondB.first;}void prints(){ printf("%d %d/n",n,sum>>1); if(alen>0)printf("%d",ash1); for(int i=1;i0)printf("%d",ash2); for(int i=1;i0;){ int amount=0; for(int j=1;j0){ amount++; } } if(amount0;){ int amount=0; for(int j=1;j0){ amount++; } } if(amount=n)failed=true; sum+=deg[i].first; } if(sum&1)failed=true; if(failed||!rebuild()){ puts("IMPOSSIBLE"); } else if(single){ puts("UNIQUE"); prints(); } else { puts("MULTIPLE"); prints(); rebuild2(); prints(); } } return 0;} 