#P1989. 无向图三元环计数
无向图三元环计数
题目背景
无向图 的三元环指的是一个 的一个子图 ,满足 有且仅有三个点 ,有且仅有三条边 $\langle u, v \rangle, \langle v, w \rangle, \langle w, u \rangle$。两个三元环 不同当且仅当存在一个点 ,满足 且 。
题目描述
给定一个 个点 条边的简单无向图,求其三元环个数。
输入格式
每个测试点有且仅有一组测试数据。
输入的第一行是用一个空格隔开的两个整数,分别代表图的点数 和边数 。
第 到第 行,每行两个用空格隔开的整数 ,代表有一条连接节点 和节点 的边。
输出格式
输出一行一个整数,代表该图的三元环个数。
3 3
1 2
2 3
3 1
1
5 8
1 2
2 3
3 5
5 4
4 2
5 2
1 4
3 4
5
提示
【样例 2 解释】
共有 个三元环,每个三元环包含的点分别是 $\{1, 2, 4\}, \{2, 3, 4\}, \{2, 3, 5\}, \{2, 4, 5\}, \{3, 4, 5\}$。
【数据规模与约定】
本题采用多测试点捆绑测试,共有两个子任务。
- Subtask 1(30 points):,。
- Subtask 2(70 points):无特殊性质。
对于 的数据,,,,给出的图不存在重边和自环,但不保证图连通。
【提示】
- 请注意常数因子对程序效率造成的影响。