完全多部图的判断（个人思考）

系统管理员 2021-03-29 14:00 436阅读 0赞

### 题目描述： ###

给定一张包含N个点、M条边的无向图，每条边连接两个不同的点，且任意两点间最多只有一条边。对于这样的简单无向图，如果能将所有点划分成若干个集合，使得任意两个同一集合内的点之间没有边相连，任意两个不同集合内的点之间有边相连，则称该图为完全多部图。现在你需要判断给定的图是否为完全多部图。

### 输入： ###

第一行输入一个整数T表示数据组数，1<=T<=10。

每组数据格式为：

第一行包含两个整数N和M，1<=N<1000，0<=M<=N(N-1)/2

接下来M行，每行包含两个整数X和Y，表示第X个点和第Y个点之间有一条边，1<=X,Y<=N。

### 输出： ###

每组输出占一行，如果给定的图为完全多部图，那么输出Yes，否则输出No。

### 样例输入： ###

2  
5 7  
1 3  
1 5  
2 3  
2 5  
3 4  
4 5  
3 5  
4 3  
1 2  
2 3  
3 4

### 样例输出： ###

Yes

No

### 说明： ###

这道题首先输入一个T，表示有多少组需要判断的数据。

接下来输入节点个数N和边数M，再输入边的两端节点是多少。我们可以把边的信息存储到邻接矩阵中。

先来看一下样例中的反例，1-2，2-3，3-4

如果按照题目中的准则去判断，1跟2之间有边连接，那么1跟2就不能在同一个集合中，而是要分开，构成\[\[1\],\[2\]\]两个集合。

接下来2跟3有边连接，那么2跟3就不能在一个集合中，同时1跟3之间没有边连接，那么集合只能变成\[\[1,3\],\[2\]\]。

接下来3跟4有边连接，4跟2没有边连接，4跟1没有边连接，那么这里就矛盾了，要4和2和1在同一个集合中，但是我们只能1和2之间有边连接的。

所以我们总结一下，我们可以设计两个机制来解决构建集合的问题，一个是开新集合的机制，一个是插入某个已经存在的集合的机制。

这两个机制都要包含检查步骤，确定了目前满足所有条件才可以开新集合或者插入已有集合。

举个样例1的例子，想法如下：

我们首先看点1，1只能在新的集合中，构成大集合\[\[1\]\]。

接着看点2，2和1没有边连接，那么2只能和1在同一个集合中，同时检查2能不能和其他的集合中的任意点有边连接。由于这里没有其它集合，所以插入\[1\]中，构成\[\[1,2\]\]。

接着看点3，3和每一个点都有边连接，所以3要开一个新的集合，构成\[\[1,2\],\[3\]\]这个大集合。

接着看点4，4和1没有边连接，那么似乎要把4插入到第一个集合中，构成\[\[1,2,4\],\[3\]\]，但在插入前要先检查4跟第一个集合中的所有元素是不是都没有边连接，并且检查4跟其他集合中的元素是不是都有边连接，两个条件中哪一个不能满足，那么就输出No，结束这次样例的检查。

接着看点5，5和每一个点都有边连接，所以5要开一个新的集合，构成\[\[1,2\],\[3\],\[5\]\]这样的大集合。

时间太晚了，明天再构造代码分享给大家吧。

发表评论取消回复

表情：

评论列表（有 0 条评论，436人围观）

还没有评论，来说两句吧...

相关阅读

相关二部图

多网站都喜欢让用户点击“喜欢/不喜欢”，“顶/反对”，也正是这种很简单的信息也可以利用起来对用户进行推荐！这里介绍一种基于网络结构的推荐系统！由于推荐系统深深植根于互...

妖狐艹你老母/ 2024年04月19日 11:06/ 0 赞/ 73 阅读

相关 HTTP首部字段完全解析

http协议是前端开发人员最常接触到的网络协议。在开发过程中，尤其是调试过程中避免不了需要去分析http请求的详细信息。在这其中头部字段提供的信息最多，比如通过响应状态码我们可

痛定思痛。/ 2023年06月03日 12:58/ 0 赞/ 8 阅读

相关超越图灵测试：判断机器是否在思考的现代方法

![format_png][] 全文共2189字，预计学习时长6分钟 ![format_png 1][] 图源：slate 人工智能正在改变生活的方方面面，

川长思鸟来/ 2022年12月12日 13:40/ 0 赞/ 97 阅读

相关 [编程题]iNOC产品部--完全数计算

> Talk is cheap, show me the code. 一、问题描述完全数（Perfect number），又称完美数或完备数，是一些特殊的自然数。它所

阳光穿透心脏的1/2处/ 2022年09月30日 10:58/ 0 赞/ 123 阅读

相关多思考

说实话，我现在很少写文章。自初中开始我就讨厌写文章，讨厌为了应试必须在1个小时内写出一篇文章，然后交给别人评判你的文章打多少分，那种言之无物又必须绞尽脑汁把一篇文章凑

深碍√TFBOYSˉ_/ 2022年09月22日 01:26/ 0 赞/ 145 阅读

相关英文文章写作的一点个人思考

当前国内很多研究生在英文论文写作过程中经常采用先写好中文，然后借用翻译软件转为英文的方法，这种写作手段除非万不得已切忌采用(新手可以尝试，但是后期一定要自己写，或者模仿别人写，

Bertha 。/ 2022年09月08日 11:38/ 0 赞/ 214 阅读

相关二部图（不存在奇数环的图）

Catch Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/

￡神魔★判官ぃ/ 2022年06月08日 01:24/ 0 赞/ 152 阅读

相关二部图(染色法判断二部图)

二部图时间限制：1000 ms | 内存限制：65535 KB 难度：1 描述二部图又叫二分图，我们不是求它的二分图最大匹配，也不是完美匹配，也

偏执的太偏执、/ 2022年06月08日 01:23/ 0 赞/ 197 阅读

相关 jq判断页面滚动到底部

var scrollTop = $(window).scrollTop(); var scrollHeight = $(

今天药忘吃喽~/ 2022年06月01日 14:16/ 0 赞/ 305 阅读

相关完全多部图的判断（个人思考）

题目描述：给定一张包含N个点、M条边的无向图，每条边连接两个不同的点，且任意两点间最多只有一条边。对于这样的简单无向图，如果能将所有点划分成若干个集合，使得任意两个同一...

系统管理员/ 2021年03月29日 14:00/ 0 赞/ 437 阅读