这完全图是什么图?

来源：蜘蛛抓取(WebSpider) 时间：2018-11-10 21:08 标签： P图

　　给你一个包含 n 个点m 条边的無向图，判断是否存在三点 x,y,z满足：

　　　　x与y , y与z 有边，但是 x与z 无边；

　　如果存在输出 "NO"，反之输出 "YES"；

　　整个图可划分成若干个联通子图，判断这若干个连通子图是否为完全图即可；

　　如果存在某个联通子图为非完全图那么，肯定会找但满足上述条件的 x,y,z输出 "NO"；

　　反之，输出 "YES"；

　　求解图是否为完全图我在模拟赛的时候，用出度判断的；

　　那么我可以用 DFS 在 O(x) 的时间复杂度内求出每个点的出喥（或入度），这 x 个点的出度和应该等于 $x\cdot (x-1)$;

　　如果等于则表明这个图为完全图，反之为非完全图；

　　另一种求解完全图的方法，特別简洁by mxl（偷偷看她代码 tql）；

　　不过，需要用 $vector$ 存图；

　　假设 a,b,c,d 构成一个完全图那么，$vector$ 中存储的信息如下：

　　此时你可发现不了什麼，但是如果 $vector_i$ 中额外加入其自身 i 呢？

　　这是你会发现，对于完全图中的所有点其指向的其他节点的信息完全相同；

　　所以，判斷某图是否为完全图时只需要判断在同一个图中的所有节点，$vector$ 中是否保存相同的信息即可；

　　这样是不是每个节点都需将 $vector$ 中的信息遍曆一遍那这样岂不太耗时了 ；

　　（2）存在 $vector$ 中的最小的节点是否相同

我要回帖

更多关于 P图 的文章

 

随机推荐