hdu 2454 Degree Sequence of Graph G (推断简单图)
简单 of HDU sequence Graph 推断
2023-09-27 14:27:02 时间
///已知各点的度,推断是否为一个简单图 #include<stdio.h> #include<algorithm> #include<string.h> using namespace std; int a[1010]; bool cmp(int x,int y) { return x>y; } int main() { int t,n,i,j; scanf("%d",&t); while(t--) { int flag=1; scanf("%d",&n); for (i=0; i<n; i++) scanf("%d",&a[i]); sort(a,a+n,cmp); while (a[0] && a[n-1]>=0) { int i = 1; while (a[0]--) { --a[i++]; } ++a[0]; sort(a,a+n,cmp); } if(a[n-1]<0) printf("no\n"); else printf("yes\n"); } return 0; }
1。Havel-Hakimi定理主要用来判定一个给定的序列是否是可图的。
2。首先介绍一下度序列:若把图 G 全部顶点的度数排成一个序列 S。则称 S 为图 G 的度序列。
3,一个非负整数组成的有限序列假设是某个无向图的序列,则称该序列是可图的。
4,判定过程:(1)对当前数列排序,使其呈递减,(2)从S【2】開始对其后S【1】个数字-1,(3)一直循环直到当前序列出现负数(即不是可图的情况)或者当前序列全为0 (可图)时退出。
5,举例:序列S:7,7,4,3,3,3,2,1 删除序列S的首项 7 。对其后的7项每项减1,得到:6,3,2,2,2,1,0,继续删除序列的首项6,对其后的6项每项减1。得到:2,1,1,1,0,-1。在这一点上已经出现了负。因此,序列图不可。
版权声明:本文博客原创文章,博客,未经同意,不得转载。
相关文章
- C#中缓存的使用 ajax请求基于restFul的WebApi(post、get、delete、put) 让 .NET 更方便的导入导出 Excel .net core api +swagger(一个简单的入门demo 使用codefirst+mysql) C# 位运算详解 c# 交错数组 c# 数组协变 C# 添加Excel表单控件(Form Controls) C#串口通信程序
- 1009 Product of Polynomials (25 分)【难度: 简单 / 知识点: 模拟】
- 《C++程序设计教程(第3版)》——第1章,第4节简单的C++程序介绍
- mysql8.0安装教程与配置(最详细)操作简单
- Python网络爬虫 - 一个简单的爬虫例子
- 超简单集成HMS ML Kit 人脸检测实现可爱贴纸
- MS COCO数据集介绍以及pycocotools简单使用
- 预处理的简单原理
- 有哪些简单好用,但学校不教的 SQL 语法?
- Linux下TCP通信简单实例
- Python 基础 之 多任务 gevent 协程应用的简单案例,简单实现下载网上文件的功能(urllib,gevent 等)
- 在Eclipse上实现简单的JDBC增删查改操作
- leetcode 191. Number of 1 Bits 位1的个数(简单)
- leetcode 697. Degree of an Array 数组的度(简单)