建设个人网站步骤,百度快速提交入口,查询网站相关网址,wordpress系统教程 pdf三元环计数
问题
给出一张n个点m条边的无向图#xff0c;问图中有多少个三元组{ u , v , w } #xff0c;满足图中存在 { (u,v) , (v,w) , (w,u) } 三条边。
求解
Step1 定向
将所有点按 度数 从小到大排序#xff0c;如果度数相同按 点编号 从小到大排序#xff0c;u…三元环计数
问题
给出一张n个点m条边的无向图问图中有多少个三元组{ u , v , w } 满足图中存在 { (u,v) , (v,w) , (w,u) } 三条边。
求解
Step1 定向
将所有点按 度数 从小到大排序如果度数相同按 点编号 从小到大排序u的排名记作 rnkurnk_urnku。
将这张图转化为有向图对于一条无向边 x − y 若 rnkxrnkyrnk_xrnk_yrnkxrnky那么就将这条无向边变成 x → y 。反之则反之。
这样转化后这张图一定是 有向无环图 。
证明
使用反证法假设有一个环a→b→c→aa\to b \to c \to aa→b→c→a 那么有设 x 的度数为 dxd_xdx da≥db≥dc≥dad_a \geq d_b \geq d_c \geq d_ada≥db≥dc≥da要使该不等式成立当且仅当满足 dadbdcdad_a d_b d_c d_adadbdcda。
设 x 的编号为 idxid_xidx那么有idaidbidcidaid_aid_bid_cid_aidaidbidcida即 idaidaidaidaid_a id_a id_a id_aidaidaidaida该式子不成立故假设不成立证毕。
Step2 暴力枚举
枚举一个点 u 和它的所有出边到的点 v 并标记再枚举 v 的出边到的点 w如果 w 也有标记则表示找到了一个三元环 这样每个三元环只会在 u 被统计一次rnkurnk_urnku在三元环中是最大的
Code
#includeiostream
#includecstdio
using namespace std;
const int N1e55;
const int M2e55;
struct Edge{int v,nxt;
}edge[M1];
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].vv;edge[cnt].nxthead[u];head[u]cnt;
}
bool cmp(int a,int b){if(d[a]d[b]) return ab;return d[a]d[b];
}
int main(){scanf(%d%d,n,m);for(int i1;im;i){scanf(%d%d,a[i],b[i]);d[a[i]];d[b[i]];}for(int i1;im;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 u1;un;u){for(int ihead[u];i;iedge[i].nxt) mark[edge[i].v]u;for(int ihead[u];i;iedge[i].nxt){int vedge[i].v;for(int jhead[v];j;jedge[j].nxt){int wedge[j].v;if(mark[w]u) ans;}}}printf(%d\n,ans);return 0;
} 时间复杂度
考虑每一条边被遍历的次数对于一条边 x→yx\to yx→y他被遍历的次数为 inxin_xinx 。inxin_xinx表示 x 的入度那么总的时间复杂度就是每一条边的 inxin_xinx 之和。
又可以发现inxin_xinx 的上限就是 m\sqrt mm因为要求每个连向 x 的点的度都大于 inxin_xinx 也就是说有 inxin_xinx 个点的度数大于inxin_xinx这样就至少需要 inx2in_x^2inx2 条边所以 inx2≤m⇒inx≤min_x^2\leq m ⇒ in_x \leq \sqrt minx2≤m⇒inx≤m
所以总时间复杂度 O(mm)O(m\sqrt m)O(mm)
四元环计数
问题
给出一张n个点m条边的无向图问图中有多少个四元组{ u , v , w x } 满足图中存在 { (u,v) , (v,w) , (w,x)(x,u) } 四条边。
求解
Step1 定向
同三元组计数
Step2 暴力枚举
枚举一个点 u 和它的所有 出边 到的点 v 然后枚举 v 的 无向边 到的点 w其中要求 rnkurnkwrnk_urnk_wrnkurnkw
每访问到一个 w 给答案加上 w 的标记并给 w 的标记加 1 这样每个四元环只会在 u 被统计一次rnkurnk_urnku在四元环中是最大的
Code
#includeiostream
#includecstdio
using namespace std;
const int N1e55;
const int M2e55;
inline int read(){int x0,f1;char chgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){xx*10ch-0;chgetchar();}return x*f;
}
struct Edge{int v,nxt;
}edge[M1],e[M1];
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].vv;edge[cnt].nxthead[u];head[u]cnt;
}
void add_e(int u,int v){e[ct].vv;e[ct].nxthd[u];hd[u]ct;
}
bool cmp(int a,int b){if(d[a]d[b]) return ab;return d[a]d[b];
}
int main(){nread();mread();for(register int i1;im;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 i1;im;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]);}ans0;for(register int u1;un;u){for(register int ihead[u];i;iedge[i].nxt){int vedge[i].v;for(register int jhd[v];j;je[j].nxt){int we[j].v;if(d[u]d[w]||(d[u]d[w]uw)){ans1ll*tmp[w];tmp[w];}}}for(register int ihead[u];i;iedge[i].nxt){int vedge[i].v;for(register int jhd[v];j;je[j].nxt){int we[j].v;if(d[u]d[w]||(d[u]d[w]uw)) tmp[w]0;}}}printf(%lld\n,ans);return 0;
}时间复杂度
O(mm)O(m\sqrt m)O(mm)
证明自己想的不保证对
对于边x−yx - yx−y假设它定向后为 x→yx \to yx→y 那么作为无向边它被遍历 inxinyin_xin_yinxiny 次作为有向边被遍历 inxin_xinx 次总过被遍历 2inxiny2in_xin_y2inxiny 次
总复杂度仍是 O(mm)O(m\sqrt m)O(mm)
