P40082

[模板]无向图三元环计数

难度 6 级 有向无环图 拓扑排序 图论
讨论 统计 2通过 3提交 66.7%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

无向图 G 的三元环指的是一个 G 的一个子图 G_0,满足 G_0 有且仅有三个点 u, v, w,有且仅有三条边 \langle u, v \rangle, \langle v, w \rangle, \langle w, u \rangle。两个三元环 G_1, G_2 不同当且仅当存在一个点 u,满足 u \in G_1 且 u \notin G_2。

输入

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

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

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

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

输出

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

样例

样例 1
输入
3 3
1 2
2 3
3 1
输出
1
样例 2
输入
5 8
1 2
2 3
3 5
5 4
4 2
5 2
1 4
3 4
输出
5

提示

样例二解释 共有 5 个三元环,每个三元环包含的点分别是 {1, 2, 4}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}。

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交