文章目录

基环树无向基环树内向基环树外向基环树

基环树

无向基环树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rSJ5RTND-1601904376773)(C:\Users\lin\Desktop\QQ截图20201005211846.png)]

找环代码

#include <iostream> #include <algorithm> #include <cstring> #include <string> using namespace std; const int N = 1e5+10; int h[N],e[2*N],ne[2*N],val[2*N],idx; int dfn[N],id;//时间戳 int pre[N];//记录它的父亲是谁 int loop[N],cnt; //无向图做法 void dfs_1(int u) { dfn[u] = ++id; for(int i=h[u];~i;i=ne[i]) { int j = e[i]; if(j==pre[u])continue; if(dfn[j]) { if(dfn[j]<dfn[u])continue; //找到闭环 u可以到达比它大的点 loop[++cnt] = j; for(;j!=u;j=pre[j])loop[++cnt] = pre[j]; return ; } else pre[j] = u,dfs_1(j); } return ; }

内向基环树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-N5lrZ2sB-1601904376775)(C:\Users\lin\Desktop\QQ截图20201005211953.png)]

每一个点的出度都为1

void dfs(int u) { dfn[u] = ++id; if(dfn[e[u]])mark = u;//找到环上一点 else dfs(e[u]); }

外向基环树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-11IB2IMq-1601904376778)(C:\Users\lin\Desktop\QQ截图20201005212029.png)]

每一个点的出度都为1

这找环和内向基环树找环方法一样 只要反向建图就可以