参考文章：
不常用的黑科技——「三元环」

引入

给定一张无重边，无自环的无向图，点数为n，边数为m，且n，m同阶，问有多少个无序三元组(i,j,k),使得存在：

有一个连接i，j的边

有一条连接j，k的边

有一条链接k，i的边
即三元环

解决方法：

首先对所有的无向图进行定向，对于任意一条边，从度数大的点连向度数小的点，当度数一样时，从编号小的点连向编号大的点

此时就得到一个有向无环图

然后枚举每一个点，将u所有到达的点v进行标记，标记为u,然后再遍历点v，枚举点v所能到达的点w，如果w存在被u访问的标记，则说明(u,v,w)是一个三元环

证明：

这里讲的很详细，我就不做赘述
不常用的黑科技——「三元环」

复杂度

$O(n+m+n\sqrt{m}+m\sqrt{m})=O(m\sqrt{m})$

代码：

#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; vector<int> g[N]; int deg[N], vis[N], n, m, ans; struct E { int u, v; } e[N * 3]; int main() {scanf("%d%d", &n, &m);for(int i = 1 ; i <= m ; ++ i) {scanf("%d%d", &e[i].u, &e[i].v);++ deg[e[i].u], ++ deg[e[i].v];}for(int i = 1 ; i <= m ; ++ i) {int u = e[i].u, v = e[i].v;if(deg[u] < deg[v] || (deg[u] == deg[v] && u > v)) swap(u, v);g[u].push_back(v);}for(int x = 1 ; x <= n ; ++ x) {for(auto y: g[x]) vis[y] = x;for(auto y: g[x])for(auto z: g[y])if(vis[z] == x)++ ans;}printf("%d\n", ans); }

总结

以上是生活随笔为你收集整理的三元环讲解的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。