參考文章：
不常用的黑科技——「三元環(huán)」

引入

給定一張無重邊，無自環(huán)的無向圖，點數(shù)為n，邊數(shù)為m，且n，m同階，問有多少個無序三元組(i,j,k),使得存在：

有一個連接i，j的邊

有一條連接j，k的邊

有一條鏈接k，i的邊
即三元環(huán)

解決方法：

首先對所有的無向圖進行定向，對于任意一條邊，從度數(shù)大的點連向度數(shù)小的點，當(dāng)度數(shù)一樣時，從編號小的點連向編號大的點

此時就得到一個有向無環(huán)圖

然后枚舉每一個點，將u所有到達的點v進行標(biāo)記，標(biāo)記為u,然后再遍歷點v，枚舉點v所能到達的點w，如果w存在被u訪問的標(biāo)記，則說明(u,v,w)是一個三元環(huán)

證明：

這里講的很詳細，我就不做贅述
不常用的黑科技——「三元環(huán)」

復(fù)雜度

$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); }

總結(jié)

以上是生活随笔為你收集整理的三元环讲解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。