求原图T^T

点击联系发帖人 时间：2016-05-20 19:53

如何求T

给定一个无自环重边的无向图求这个图的三元环¹
的个数以及补图²的三元环个数。

2.2 输入格式第一行 2 个数n,m 分别表示图的点数、边数。

接下来 m行每行两个数 u, v ，表示一条连接u, v 的无向边

2.3 输出格式一行两个数，依次表示原图的三元环个数以及补图的三元环的个数

2.7 评分方式如果你两个数均输出正确，得 10分

否則如果两个数中任意一个正确或者两个数的和正确，得 6 分

1大小为 3的环。即一个无序三元组 (x, y, z) 使得任意两点之间都有边

2一条连接(u, v)(u = v) 的边如果茬原图中出现了，那么在补图中不会出现否则一定会在补图中出现。

直接求两个图的三元环个数并不好求那么如果我们知道了原图和補图三元环个数的和，则只要求其中一种就行了

但是直接求和也不好求，这时我们可以求那些既不存在于原图也不存在于补图的三元环個数

可知这些三元环一定是至少有一条边在原图，至少有一条边在补图的于是它们在两图中都是残缺的。

那么我们记录一下每个点在原图中的度d[i]d[i]*(n-1-d[i])就是经过i点的不在原图也不在补图的三元环个数。（一条边在原图一条边不在n-1-d[i]为i在补图中的度）

由于我们对每个点都进行叻计算，所以算出来的值是两倍的需要除以2。

全图中三元环个数为用它减去我们算出来的值就得出了原图和补图三元环个数之和。

现茬我们开始统计原图中三元环个数直接暴力枚举有共点的两条边，然后查找另外两个点有木有边

我是用的小PO的先把边按照双关键字排序然后二分查找的方法。由于记的是单向边所以不用除以2

}

太巧了我刚刚在看p站，刚刚好看到这图。作者是Jinko_神子

你对这个回答的评价是

下载百度知道APP，抢鲜体验

使用百度知道APP立即抢鲜体验。你的手机镜头里或许有别人想知道的答案

}

上面图片后面不是给你链接了,自巳去下载

那就没办法了,链接贴出来就自动变成这样估计你是手机

你对这个回答的评价是？

下载百度知道APP抢鲜体验

使用百度知道APP，立即搶鲜体验你的手机镜头里或许有别人想知道的答案。

}