专栏首页chenjx85的技术专栏完全多部图的判断(个人思考)

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

题目描述:

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

相关文章

  • leetcode-914-卡牌分组

    1、这道题给定一个vector,vector中存放着卡牌的数字,比如1、2、3、4这样子,你需要把这些卡牌分成多组。

    chenjx85
  • leetcode-771-Jewels and Stones(建立哈希表,降低时间复杂度)

    chenjx85
  • leetcode-166-分数到小数(用余数判断有没有出现小数的循环体)

    给定两个整数,分别表示分数的分子 numerator 和分母 denominator,以字符串形式返回小数。

    chenjx85
  • 4.93Python数据类型之(8)集合

    py3study
  • .Net多线程编程—并发集合

    并发集合 1 为什么使用并发集合? 原因主要有以下几点: System.Collections和System.Collections.Generic名称空间中所...

    甜橙很酸
  • Java SE | 每日作业卷day15

    自定义一个学生类,给出成员变量name和age,使用HashSet集合存储自定义对象并遍历,遍历集合的时候,在控制台输出学生对象的成员变量值。要求使用两种方式进...

    剑走天涯
  • [ Java学习基础 ] Java的对象容器 -- 集合

    Kevin_Zhang
  • 一文掌握Python集合的语法与应用

    Python语言中的集合是无序的、可变的容器类对象,所有元素放在一对大括号中,元素之间使用逗号分隔,同一个集合内的每个元素都是唯一的,不允许重复。

    Python小屋屋主
  • 码农眼中的数学之~数学基础

    1维直线、2维平面(长宽)、3维空间(长宽高 | xyz轴)、4维时空(xyz轴+时间轴)

    逸鹏
  • 排队的时候请学习List 不要做Set

    集合框架是一个非常重要的知识点,有了集合框架,我们在处理一些特殊的数据结构的时候,可以直接用框架封装好的工具来帮助我们解决问题。

    用户5745563

扫码关注云+社区

领取腾讯云代金券