完全多部图的判断(个人思考)

题目描述:

给定一张包含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 条评论
登录 后参与评论

相关文章

来自专栏CDA数据分析师

入门 | 数据科学初学者必知的NumPy基础知识

NumPy(Numerical Python)是 Python 中的一个线性代数库。对每一个数据科学或机器学习 Python 包而言,这都是一个非常重要的库,S...

14020
来自专栏尾尾部落

[算法总结] 二分查找

二分查找法作为一种常见的查找方法,将原本是线性时间提升到了对数时间范围,大大缩短了搜索时间,但它有一个前提,就是必须在有序数据中进行查找。

22920
来自专栏杂七杂八

numpy.nonzero()函数

官方文档如下: numpy.nonzero(a) Return the indices of the elements that are non-zero....

24730
来自专栏desperate633

LintCode 搜索插入位置题目分析代码

给定一个排序数组和一个目标值,如果在数组中找到目标值则返回索引。如果没有,返回到它将会被按顺序插入的位置。 你可以假设在数组中无重复元素。

8720
来自专栏算法修养

LeetCode 126 Word Ladder II

具体的思路是,分别从起始和结束字符串出发两遍BFS, 得到每个点到起始字符串的最短距离和终点字符串的最短距离。 然后再从起始字符串出发,DFS 寻找路径。由于...

12520
来自专栏数据结构与算法

1116 四色问题

1116 四色问题  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解 题目描述 Description 给定N(小于...

29550
来自专栏章鱼的慢慢技术路

求 pi 的近似值题型汇总

24470
来自专栏尾尾部落

[剑指offer] 调整数组顺序使奇数位于偶数前面

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相...

10820
来自专栏Python小屋

详解Python列表推导式

列表推导式,也叫列表解析式,英文名称为list comprehension,可以使用非常简洁的方式来快速生成满足特定需求的列表,代码具有非常强的可读性。另外,P...

38440
来自专栏C语言及其他语言

【每日一题】问题 1472: 矩阵乘法

关注我们 题目描述 给定一个N阶矩阵A,输出A的M次幂(M是非负整数) 例如: A = 1 2 3 4 A的2次幂 7 10 ...

335100

扫码关注云+社区

领取腾讯云代金券