参考:https://oi-wiki.org/graph/rings-count/
求四元环步骤:
- 建双向边。
- 给每条边定向,由度数小的点指向大的,若度数一样则看编号大小。
- 此时只有这几种情况:
都可以归类为:
- 枚举起始点 A,枚举 A <--> B(双向边),枚举 B --> C,让 C 点被访问次数 \(cnt\) 加 \(1\)。
- 四元环数量即为 \(cnt[i]*(cnt[i]-1) / 2\)
时间复杂度 \(O(n \sqrt n)\)。
具体复杂度证明和三元环求解见 OI WIKI。
代码
// Problem: #191. 无向图四元环计数
// Contest: LibreOJ
// URL: https://loj.ac/p/191
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// Author: Eason
// Date:2024-02-24 18:13:33
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define INF 0x3f3f3f3f
#define re register
#define il inline
#define gc getchar
inline int read() {
int f = 1, k = 0;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
k = (k << 1) + (k << 3) + (c ^ 48), c = getchar();
return k * f;
}
const int N = 2e5 + 5;
int n, m, deg[N];
vector<int> v[N], v1[N];
int cnt[N];
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u = read(), v = read();
v1[u].push_back(v);
v1[v].push_back(u);
deg[u] ++, deg[v] ++;
}
for (int i = 1; i <= n; i++)
for (int j : v1[i])
if (deg[i] < deg[j] || (deg[i] == deg[j] && i < j))
v[i].push_back(j);
int res = 0;
for (int i = 1; i <= n; i++) {
for (int j : v1[i])
for (int k : v[j])
if (deg[i] < deg[k] || (deg[i] == deg[k] && i < k))
res += cnt[k]++;
for (int j : v1[i])
for (int k : v[j])
cnt[k] = 0;
}
cout << res << endl;
return 0;
}
// Problem: P1989 无向图三元环计数
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1989
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Author: Eason
// Date:2024-02-24 18:06:06
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define INF 0x3f3f3f3f
#define re register
#define il inline
#define gc getchar
inline int read()
{
int f=1,k=0;
char c = getchar();
while (c <'0' || c > '9')
{
if (c=='-') f=-1;
c=getchar();
}
while(c >= '0' && c <= '9') k = (k << 1)+(k << 3)+(c^48),c=getchar();
return k*f;
}
const int N = 2e5+5;
int n,m,deg[N];
vector<int> v[N],v1[N];
bool vis[N];
int main()
{
cin >> n >> m;
for (int i = 1;i <= m;i++)
{
int u = read(),v = read();
v1[u].push_back(v);v1[v].push_back(u);
deg[u]++,deg[v]++;
}
for (int i = 1;i <= n;i++)
for (auto j : v1[i])
if (deg[i] < deg[j] || (deg[i] == deg[j] && i < j)) v[i].push_back(j);
int cnt = 0;
for (int i = 1;i <= n;i++)
{
for (int j :v[i]) vis[j] = 1;
for (int j:v[i])
for (int k : v[j]) if (vis[k]) cnt++;
for (int j :v[i]) vis[j] = 0;
}
cout << cnt << endl;
return 0;
}
标签:图论,int,long,四元,无向,https,getchar,define
From: https://www.cnblogs.com/codwarm/p/18030480