Havel-Hakimi 度序列判断无向图是否可图 Poj 1659 Frogs' Neighborhood

一时失言乱红尘 2022-09-19 04:13 128阅读 0赞

南京现场赛遇到的知识点，旁边北邮队伍秒过，我们这边三人大眼瞪小眼。。。赛后证明最后队友思路大方向没错，只是判断是否存在多种构图方式时有问题。

以下摘自百度知道：

Havel-Hakimi算法用来判断是否可以构造出一个满足给定顶点序列的图。例如给一个非升整数序列(4, 3, 2, 2, 2，1)，该算法将判断能不能找到一个具有4个顶点的图且顶点的度可以构成上述序列。算法最终会构造出如下的图。

算法也很简单。

给定非升序列(d0, d1, d2, d3, .. dn)，算法从一个有n个点没有边的图开始。n个节点与n个度一一对应。

每一次，找出还没有满足节点度要求的所有节点，按照剩余度非升排序。取出第一个节点，设其剩余度为k，则将其与随后的k个点分别连边。更新节点剩余度，如果出现负值则说明无法构造。

重复上述步骤直至所有点都满足度要求或者判定无法构造图。

![SouthEast][]

该过程的具体实现可以参考：http://sbp810050504.blog.51cto.com/2799422/883904

还有一个优化：所有度之和为偶数才可图。

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    bool edge[15][15];
    
    struct Node
    {
    	int degree;
    	int id;
    	void Get (int a)
    	{
    		scanf("%d",&degree);
    		id=a;
    	}
    	bool operator < (const Node b) const
    	{
    	    return degree>b.degree;
    	}
    }data[30];
    
    int main ()
    {
    	int T,n,i,j;
    	scanf("%d",&T);
    	while (T--)
    	{
    		bool flag=true;
    		scanf("%d",&n);
    		memset(edge,false,sizeof(edge));
    		for (i=0;i<n;i++)
    			data[i].Get(i);
    		for (i=0;i<n;i++)
    		{
    			sort(data,data+n);
    			int tmp=data[0].degree;
    			data[0].degree=0;
    			if (tmp==0) break;
    			else
    				for (j=1;j<=tmp;j++)
    				{
    					data[j].degree--;
    					if (data[j].degree<0)
    					{
    						flag=false;
    						break;
    					}
    					else
    					{
    						edge[data[0].id][data[j].id]=true;//第一个与后面k个相连
    						edge[data[j].id][data[0].id]=true;
    					}
    				}
    			if (flag==false) break;
    		}
    		if (flag)
    		{
    			printf("YES\n");
    			for (i=0;i<n;i++)
    				for (j=0;j<n;j++)
    					printf(j==n-1?"%d\n":"%d ",edge[i][j]);
    		}
    		else
    			printf("NO\n");
    		printf("\n");
    	}
    	return 0;
    }

[SouthEast]: /images/20220828/61ada840980d400b8ac27a0628890a4e.png