洛谷P6057 [加油武汉] 七步洗手法 题解

题目链接：P6057 [加油武汉] 七步洗手法

题意：

给定一张含有 $n$ 个点的无向完全图，其中 $m$ 条边是白边，其余是黑边。

现在需要你求出同色的三元环（或者说，三角形）的个数。

输入格式：

第一行整数 $n,m$，意义如题。

剩下的 $m$ 行每行两个整数 $u,v$，代表白边的两个端点。保证给出的白边没有重边和自环。

输出格式：

一行一个整数，为答案。

数据范围：

满足 $1 \leq n \leq 10^5,1 \leq m \leq 3\times 10^5$。

正难则反，用三角形的总个数减去异色的个数。

因为一条边只会影响两个点，所以我们可以统计所有异色角的个数，除以 $2$ 就是异色三角形的个数

时间复杂度 $\mathcal{O}(n+m)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

int in[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m, ans = 0; cin >> n >> m;
    for(int i = 1, u, v; i <= m; i++) { cin >> u >> v; ++in[u]; ++in[v]; }
    for(int i = 1; i <= n; i++) ans += in[i] * (n - 1 - in[i]);
    cout << (n * (n - 1) * (n - 2) / 6 - ans / 2) << '\n';
    return 0;
}

---

题外话：

好消息，新冠二阳，所有能挂的消炎药都过敏。

现在只能睡大觉，或者作死继续写题了。