题目内容

小塔拿到了一个无向图，他准备选择两条边，满足这两条边的4个节点各不相同。

小塔想知道，有多少种选择边的方案？

数论

选择两条边，满足这两条边的4个节点各不相同也就是这两条边不连通暴力的方法$m^2$ 去枚举所有情况肯定是行不通的，不连通的情况不好求，但是两条边联通的答案好.所以$\\$$ans=C(m,2)-选两条边且联通的总数$$\\$选两条边且联通的总数求法就是枚举每个点,每个点$i$的贡献=$c(m_i,2),m_i=$连接点$i$的边数 $\\$$ans=C_{m}^{2}-{\sum_{i=1}^{n}}C_{m_i}^{2}$$\\$ 整体时间复杂度$o(n)$$\\$

代码如下

$cpp$

#include <bits/stdc++.h>
using namespace std;