ZOJ_3732 Graph Reconstruction HDU4797

2017-01-13 19:12:53来源:CSDN作者:Mrx_Nh人点击



Graph Reconstruction

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

Let there be a simple graph with N vertices 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 integer N (2 ≤ N ≤ 100), the number of vertices in the graph. The second line conrains N integers in which the ith item is the degree of ith vertex and each degree is between 0 and N-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 Eu1 u2 ... uEv1 v2 ... vE
Where N is the number of vertices and E is the number of edges, and {ui,vi} is the ith edge 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 Input

1065 5 5 4 4 365 4 4 4 4 363 4 3 1 2 0

Sample Output

UNIQUE1 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
题目大意:给定一个简单无向图(无环无平行边)的度序列(未必可构成图,只是度序列),问其是否可以构成一个简单无向图,如果能,判断该无
向图是否存在同构情况,如果存在输出任意两种情况即可。
Ps:HDU这个题没有spj,要去zoj交才行!!!
在这里,先介绍一个 Havel–Hakimi 算法用以判断一个度序列能否否成一个简单无向图,该算法的核心思想是递归和贪心。weki描述如下:

Let {/displaystyle S=(d_{1},/dots ,d_{n})}S=(d_{1},/dots ,d_{n}) be a finite list of nonnegative integers that is nonincreasing.

List {/displaystyle S}S is graphic if and only if the finite list {/displaystyle S'=(d_{2}-1,d_{3}-1,/dots ,d_{d_{1}+1}-1,d_{d_{1}+2},/dots ,d_{n})}S'=(d_{2}-1,d_{3}-1,/dots ,d_{{d_{1}+1}}-1,d_{{d_{1}+2}},/dots ,d_{n}) has nonnegative integers and

is graphic.

If the given list {/displaystyle S}S graphic then the theorem will be applied at most {/displaystyle n-1}n-1 times setting in each further step {/displaystyle S:=S'}S:=S'.

Note that it can be necessary to sort this list again. This process ends when the whole list {/displaystyle S'}S' consists of zeros.

In each step of the algorithm one constructs the edges of a graph with vertices {/displaystyle v_{1},/cdots ,v_{n}}v_{1},/cdots ,v_{n}, i.e. if it is possible to reduce

the list S to S', then we add edges /{v_{1},v_{2}/},/{v_{1},v_{3}/},/cdots ,/{v_{1},v_{{d_{1}+1}}/}.

When the list {/displaystyle S}S cannot be reduced to a list {/displaystyle S'}S' of nonnegative integers in any step of this approach,

the theorem proves that the list {/displaystyle S}S from the beginning is not graphic.

Havel-Hakimi算法的大意就是先将度序列S按照非递减排序,每次把最前面的一个元素d1(度数最大)取出来,在接下来连续的d1个元素都减去1,
相当于取出最大度数的顶点并将度数紧跟其后的连续d1个顶点建边,贪心。
如果在此过程中出现了负数则不是可图的,按此方法依次取最大的度数,注意每次取完并减一后再取时需要在此排序,原因就是因为可能出现同构,
比如下面的情况:
假设下面的六个点代表v1~v6的度数,则
S:4 3 3 3 3 3
取4变换后, S`:2 2 2 2 3
在次取时取3,因为虽然度数相同但其代表不同的定点,故在上一步如果不取倒数第二3(v5)而取最后一个3(v6),这样就是一种同构了!
AC代码(得去ZOJ交):
#include <bits/stdc++.h>using namespace std;const int MAXN = 100 + 7;class vertex{public:        int id, deg;};vertex ver[MAXN];int n, u[MAXN * MAXN], v[MAXN * MAXN];int m, s, t, r;bool cmp(vertex v1, vertex v2){        return v1.deg > v2.deg;}int Havel_Hakimi(){        int i, j, ans;        ans = 0;        for(int i = 0; i < n; ++i)        {                sort(ver + i, ver + n, cmp);                if(i + ver[i].deg >= n)         //简单无向图每个定点的度数最大为n-1                {                        ans = -1;                        break;                }                else if(ver[i].deg == 0)        //找到S`序列                {                        break;                }                for(j = i + 1; j <= i + ver[i].deg; ++j)                {                        ver[j].deg--;                        if(ver[j].deg < 0)      //出现负数,不满足S`序列                        {                                ans = -1;                                return ans;                        }                        u[m] = ver[i].id;                               v[m++] = ver[j].id;                }                if(j < n && ver[j].deg == ver[j-1].deg+1)       //存在同构的情况                {                        ans = 1;                        s = m - 1;               //要减一的序列中最后一个顶点的数组下标                          t = ver[j].id;           //要减一的序列中最后一个顶点后面紧挨着的顶点,本来将(i,j)建边,现在将(i,j+1)建边,同构的情况                        r = ver[j-1].id;         //要减一的序列中最后一个顶点的顶点标号                }        }        return ans;}void outputAns(){        printf("%d %d/n", n, m);        if(m == 0)                printf("/n/n");        else        {                for(int i=0; i < m; i++)                        printf("%d%c", u[i], i == m-1 ? '/n':' ');                for(int i=0; i < m; i++)                        printf("%d%c", v[i], i == m-1 ? '/n':' ');        }}int main(){        while(scanf("%d", &n) != EOF)        {                m = 0;                int odd = 0;                for(int i = 0; i < n; ++i)                {                        scanf("%d", &ver[i].deg);                        ver[i].id = i + 1;                        if(ver[i].deg & 1)                                odd++;                }                if(odd & 1)  // 奇数个奇度数,据握手定理知其不可能是一个简单无向图的度序列                {                        cout << "IMPOSSIBLE" << endl;                        continue;                }                else                {                        int mark = Havel_Hakimi();                        if(mark == -1)                        {                                cout << "IMPOSSIBLE" << endl;  //没有S`                        }                        else if(mark == 0)                        {                                cout << "UNIQUE" << endl;                                outputAns();                        }                        else                        {                                cout << "MULTIPLE" << endl;                                outputAns();                                v[s] = t;       //同构变换                                for(int i = s+1; i < m; i++)    //找到并交换同构时变换的顶点并对其变换                                {                                        if(u[i] == t)                                                u[i] = r;                                        else if(u[i] == r)                                                u[i] = t;                                        if(v[i] == t)                                                v[i] = r;                                        else if(v[i] == r)                                                v[i] = t;                                }                                outputAns();                        }                }        }        return 0;}


   

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台