三元环计数
解决方法
1.将无向边改成有向边，令度数大的点指向度数小的点；如果度数相同，就让编号大的点指向编号小的点。（这一步也可以是，度数小的点指向度数大的点；度数相同比较编号）
2.枚举一个点u。
3.标记所有u的出边可以到达的点。
4.枚举一个u的出边可以到达的点v，然后再枚举一个v的出边可以到达的点w，如果w被标记过，说明u,v,w构成三元环，ans++
正确性 & 复杂度
改成有向边之后，这一定是一个拓扑图，每个三元环的边一定形如 a->b, b->c, c->a ，所以每一个三元环会被恰好统计一次。
现在考虑复杂度。
度数大的点连向度数小的点的那种方法我不会证明复杂度，听说是$O(m\sqrt m)$。
度数小的连向度数大的那种方法是$O(m\sqrt m)$，因为我们可以证明每个点的出度是$O(\sqrt m)$的。下面我们称度数大于$\sqrt m$的为大度点，度数小于$\sqrt m$的为小度点。大度点显然不超过$\sqrt m$个，大度点的出边只能够连向大度点，所以大度点的出度至多是$\sqrt m$的；小度点在原图中的度不超过$\sqrt m$，所以给边定向后出度一定不超过$\sqrt m$。综上，所有的点的出度都是$O(\sqrt m)$的。在上面的算法中，我们先要枚举$u\to v$（也就是枚举一条边），然后枚举$v$的出度，这样的复杂度是$O(m\sqrt m)$的。
此外我们的算法过程中枚举到了每一个三元环，因此可以得到所有的三元环对应的点和边。
模板
hdu6184
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define PII pair<int,int>
#define MP make_pair
#define fir first
#define sec second
#define PB push_back
#define db long double
#define ll long long
using namespace std;
template <class T>
inline void rd(T &x) {
x=0; char c=getchar(); int f=1;
while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }
while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int N=1e5+10,M=2e5+10;
struct ed { int x,y,id; }e[M];
vector<ed> G[N];
int n,m,vis[N],ans[M];
int du[N];
ll id(int x,int y) { if(x>y) swap(x,y); return (x-1)*n+y; }
int main() {
while(~scanf("%d%d",&n,&m)) {
for(int i=1;i<=m;++i) {
int x,y; rd(x),rd(y);
e[i].x=x,e[i].y=y,e[i].id=i;
du[x]++,du[y]++;
}
for(int i=1;i<=m;++i) {
int x=e[i].x,y=e[i].y;
if(du[x]<du[y]||(du[x]==du[y]&&x<y)) swap(e[i].x,e[i].y),swap(x,y);
G[x].PB(e[i]);
}
for(int u=1;u<=n;++u) {
for(int i=0;i<G[u].size();++i) vis[G[u][i].y]=G[u][i].id;
for(int i=0;i<G[u].size();++i) {
int v=G[u][i].y;
for(int j=0;j<G[v].size();++j) {
int w=G[v][j].y;
int k=vis[w];
if(k) {
ans[k]++;
ans[G[u][i].id]++;
ans[G[v][j].id]++;
}
}
}
for(int i=0;i<G[u].size();++i) vis[G[u][i].y]=0;
}
ll tot=0;
for(int i=1;i<=m;++i) tot+=ans[i]*(ll)(ans[i]-1)/2;
printf("%lld\n",tot);
for(int i=1;i<=n;++i) G[i].clear(),du[i]=0;
for(int i=1;i<=m;++i) ans[i]=0;
}
return 0;
}
|
四元环计数
解决方法
1.枚举一个u作为四元环中编号最大的点。
2.依次枚举与u相邻的一个点v，然后枚举一个与v相邻的点w。我们记cnt[w]表示在v之前w被访问过多少次。那么每一次访问到w的时候，就ans+=cnt[w],cnt[w]++。
3.枚举完这个u之后，把所有的cnt[w]清零。注意w,v的编号必须小于u。这里，如果我们把所有的点按照度数重新标号之后，可以证明复杂度是 O(m\sqrt m) 的。
重新标号可以是度数越大编号越小，也可以是度数越小编号越小。
复杂度证明不会。
和三元环计数不同的是，我们并没有枚举出四元环上的每一个点。
模板
jzoj6199
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| for(int i=n;i>=1;--i) {
int u=id[i];
for(int j=0;j<E[u].size();++j) {
int v=E[u][j];
for(int k=0;k<E[v].size();++k) {
int w=E[v][k]; if(w==u) continue;
ans3+=vis[w],vis[w]++;
}
}
for(int j=0;j<E[u].size();++j) {
int v=E[u][j];
for(int k=0;k<E[v].size();++k) {
int w=E[v][k]; if(w==u) continue;
vis[w]=0;
}
}
for(int k=head[u];~k;k=e[k].next) {
int v=e[k].to;
E[v].PB(u);
}
}
|