三元環計數

問題

給出一張n個點m條邊的無向圖，問圖中有多少個三元組{ u , v , w } ，滿足圖中存在 { (u,v) , (v,w) , (w,u) } 三條邊。

求解

Step1 定向

將所有點按 度數 從小到大排序，如果度數相同按 點編號 從小到大排序，u的排名記作 $rn{k}_u$。

將這張圖轉化為有向圖：對于一條無向邊 x ? y ，若 $rn{k}_x>rn{k}_y$，那么就將這條無向邊變成 x → y 。反之則反之。

這樣轉化后，這張圖一定是 有向無環圖 。

證明：

使用反證法，假設有一個環：$a\to b\to c\to a$，
那么有（設 x 的度數為 $d_x$）：
$d_a\ge d_b\ge d_c\ge d_a$，要使該不等式成立，當且僅當滿足 $d_a=d_b=d_c=d_a$。

設 x 的編號為 $i{d}_x$，那么有：$i{d}_a>i{d}_b>i{d}_c>i{d}_a$，即 $i{d}_a>i{d}_a>i{d}_a>i{d}_a$，該式子不成立，故假設不成立，證畢。

Step2 暴力枚舉

枚舉一個點 u 和它的所有出邊到的點 v 并標記，再枚舉 v 的出邊到的點 w，如果 w 也有標記則表示找到了一個三元環

這樣，每個三元環只會在 u 被統計一次（$rn{k}_u$在三元環中是最大的）

Code

#include<iostream> #include<cstdio> using namespace std; const int N=1e5+5; const int M=2e5+5; struct Edge{int v,nxt; }edge[M<<1]; int n,m,head[N],cnt,a[M],b[M]; int d[N],ans,mark[N]; void add_edge(int u,int v){edge[++cnt].v=v;edge[cnt].nxt=head[u];head[u]=cnt; } bool cmp(int a,int b){if(d[a]==d[b]) return a>b;return d[a]>d[b]; } int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d",&a[i],&b[i]);d[a[i]]++;d[b[i]]++;}for(int i=1;i<=m;i++){if(d[a[i]]>d[b[i]]||(d[a[i]]==d[b[i]]&&a[i]>b[i]))add_edge(a[i],b[i]);else add_edge(b[i],a[i]);}for(int u=1;u<=n;u++){for(int i=head[u];i;i=edge[i].nxt) mark[edge[i].v]=u;for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].v;for(int j=head[v];j;j=edge[j].nxt){int w=edge[j].v;if(mark[w]==u) ans++;}}}printf("%d\n",ans);return 0; }

時間復雜度

考慮每一條邊被遍歷的次數：對于一條邊 $x\to y$，他被遍歷的次數為 $i{n}_x$ 。（$i{n}_x$表示 x 的入度），那么總的時間復雜度就是每一條邊的 $i{n}_x$ 之和。

又可以發現，$i{n}_x$ 的上限就是 $\sqrt{m}$，因為要求每個連向 x 的點的度都大于 $i{n}_x$ ，也就是說，有 $i{n}_x$ 個點的度數大于$i{n}_x$，這樣就至少需要 $i{n}_x^2$ 條邊，所以 $i{n}_x^2\le m?i{n}_x\le \sqrt{m}$

所以總時間復雜度 $O(m\sqrt{m})$

四元環計數

問題

給出一張n個點m條邊的無向圖，問圖中有多少個四元組{ u , v , w ，x } ，滿足圖中存在 { (u,v) , (v,w) , (w,x)，(x,u) } 四條邊。

求解

Step1 定向

同三元組計數

Step2 暴力枚舉

枚舉一個點 u 和它的所有 出邊 到的點 v ，然后枚舉 v 的 無向邊 到的點 w，其中要求 $rn{k}_u>rn{k}_w$

每訪問到一個 w 給答案加上 w 的標記，并給 w 的標記加 1

這樣，每個四元環只會在 u 被統計一次（$rn{k}_u$在四元環中是最大的）

Code

#include<iostream> #include<cstdio> using namespace std; const int N=1e5+5; const int M=2e5+5; inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } struct Edge{int v,nxt; }edge[M<<1],e[M<<1]; int n,m,head[N],cnt,hd[N],ct,a[M],b[M]; int d[N],mark[N],tmp[N]; long long ans; void add_edge(int u,int v){edge[++cnt].v=v;edge[cnt].nxt=head[u];head[u]=cnt; } void add_e(int u,int v){e[++ct].v=v;e[ct].nxt=hd[u];hd[u]=ct; } bool cmp(int a,int b){if(d[a]==d[b]) return a>b;return d[a]>d[b]; } int main(){n=read();m=read();for(register int i=1;i<=m;i++){a[i]=read();b[i]=read();d[a[i]]++;d[b[i]]++;add_e(a[i],b[i]);add_e(b[i],a[i]);}for(register int i=1;i<=m;i++){if(d[a[i]]>d[b[i]]||(d[a[i]]==d[b[i]]&&a[i]>b[i]))add_edge(a[i],b[i]);elseadd_edge(b[i],a[i]);}ans=0;for(register int u=1;u<=n;u++){for(register int i=head[u];i;i=edge[i].nxt){int v=edge[i].v;for(register int j=hd[v];j;j=e[j].nxt){int w=e[j].v;if(d[u]>d[w]||(d[u]==d[w]&&u>w)){ans+=1ll*tmp[w];tmp[w]++;}}}for(register int i=head[u];i;i=edge[i].nxt){int v=edge[i].v;for(register int j=hd[v];j;j=e[j].nxt){int w=e[j].v;if(d[u]>d[w]||(d[u]==d[w]&&u>w)) tmp[w]=0;}}}printf("%lld\n",ans);return 0; }

時間復雜度

$O(m\sqrt{m})$

證明（自己想的，不保證對）：

對于邊$x?y$，假設它定向后為 $x\to y$，
那么作為無向邊它被遍歷 $i{n}_x+i{n}_y$ 次，作為有向邊被遍歷 $i{n}_x$ 次，總過被遍歷 $2i{n}_x+i{n}_y$ 次

總復雜度仍是 $O(m\sqrt{m})$

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。