可图(Graphic)
什么是可图,那需要先说一下度序列。
度序列是把图的多有顶点度数排列成一个序列s,则称s为图G的度序列。
度序列可以是按照顶点的顺序排列,也可以按照递增、递减的顺序排列。所谓的可图,是建立在度序列的基础上的。
序列是可图的:一个非负整数组成的有限序列如果是某个无向图的度序列,则称这个序列是可图的。
说白了,就是如果一串度序列可以逆向生成出图,就是可图的。而判断一个序列是否是可图的,则由Havel-Hakimi定理判断。
Havel-Hakimi定理
由非负整数组成的非增序列s:d1,d2,...,dn(n>=2,d1>=1)是可图的,当且仅当序列:
s1:d2 - 1,d3 - 1,...,dd1+1 - 1,dd1+2,...,dn
是可图的。序列s1中有n-1个非负整数,s序列中d1后的前d1个度数(即d2~dd1+1)减1后构成s1中的前d1个数。
说白了就是先把第一个点(度数为d1)连线到后面d1个点,保证第一个点度数满足,然后再以此类推考虑后面的点。如果后面所有顶点满足并且度数不多不少(最后不剩,过程中没有度数为负数),即可认为,度序列是可图的。
青蛙邻居问题
POJ1659 Frogs' Neighborhood
Description
未名湖附近共有N个大小湖泊L1, L2, ..., Ln(其中包括未名湖),每个湖泊Li里住着一只青蛙Fi(1 ≤ i ≤ N)。如果湖泊Li和Lj之间有水路相连,则青蛙Fi和Fj互称为邻居。现在已知每只青蛙的邻居数目x1, x2, ...,xn,请你给出每两个湖泊之间的相连关系。
Input
第一行是测试数据的组数T(0 ≤ T ≤ 20)。每组数据包括两行,第一行是整数N(2 1, x2,..., xn(0 ≤ xi ≤ N)。
Output
对输入的每组测试数据,如果不存在可能的相连关系,输出"NO"。否则输出"YES",并用N×N的矩阵表示湖泊间的相邻关系,即如果湖泊i与湖泊j之间有水路相连,则第i行的第j个数字为1,否则为0。每两个数字之间输出一个空格。如果存在多种可能,只需给出一种符合条件的情形。相邻两组测试数据之间输出一个空行。
代码实现
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int G[20][20];
struct Node
{
int dnum;
int no;
}d[20];
int cmp(Node a,Node b)
{
return a.dnum > b.dnum;
}
int main()
{
int N;
cin >> N;
while(N--)
{
bool flag = 1;
memset(G,0,sizeof(G));
int n;
cin >> n;
for(int i = 0;i < n;i++)
{
cin >> d[i].dnum;
d[i].no = i;
}
for(int i = 0;i < n;i++)
{
sort(&d[i],&d[i] + n - i,cmp);
int last = d[i].dnum;
d[i].dnum = 0;
if(last > n - i)
{
flag = 0;
break;
}
for(int j = i + 1;j <= i + last;j++)
{
if(d[j].dnum - 1 >= 0)
{
G[d[i].no][d[j].no] = 1;
G[d[j].no][d[i].no] = 1;
d[j].dnum -= 1;
}else
{
flag = 0;
}
if(!flag)
break;
}
if(!flag)
break;
}
if(flag)
{
for(int i = 0;i < n;i++)
if(d[i].dnum > 0)
flag = 0;
}
if(!flag)
cout << "NO" << endl;
else
{
cout << "YES" << endl;
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
cout << G[i][j] << (j < n - 1 ? ' ' : 'n');
}
if(N)
cout << endl;
}
return 0;
}
注意
这个题目是Special Judge,也就是说这个题的答案是有多种的。这个是由Havel-Hakimi定理导致的,由于可图是由度数重构图,这个过程构建的图可能不是唯一的。