#P1989. 无向图三元环计数

无向图三元环计数

题目背景

无向图 GG 的三元环指的是一个 GG 的一个子图 G0G_0,满足 G0G_0 有且仅有三个点 u,v,wu, v, w,有且仅有三条边 $\langle u, v \rangle, \langle v, w \rangle, \langle w, u \rangle$。两个三元环 G1,G2G_1, G_2 不同当且仅当存在一个点 uu,满足 uG1u \in G_1uG2u \notin G_2

题目描述

给定一个 nn 个点 mm 条边的简单无向图,求其三元环个数。

输入格式

每个测试点有且仅有一组测试数据。

输入的第一行是用一个空格隔开的两个整数,分别代表图的点数 nn 和边数 mm

22 到第 (m+1)(m + 1) 行,每行两个用空格隔开的整数 u,vu, v,代表有一条连接节点 uu 和节点 vv 的边。

输出格式

输出一行一个整数,代表该图的三元环个数。

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 解释】

共有 55 个三元环,每个三元环包含的点分别是 $\{1, 2, 4\}, \{2, 3, 4\}, \{2, 3, 5\}, \{2, 4, 5\}, \{3, 4, 5\}$。

【数据规模与约定】

本题采用多测试点捆绑测试,共有两个子任务

  • Subtask 1(30 points):n500n \le 500m103m \le {10}^3
  • Subtask 2(70 points):无特殊性质。

对于 100%100\% 的数据,1n1051 \le n \le 10^51m2×1051 \le m \le 2 \times {10}^51u,vn1 \le u, v \le n,给出的图不存在重边和自环,但不保证图连通

【提示】

  • 请注意常数因子对程序效率造成的影响。