标签：dep vis int void dfs 基环树 fa
找环
无向图
拓扑排序找环
点击查看代码
bool vis[N];
queue<int> q;
void tp()
{
for(int i=1;i<=n;i++) if(du[i]==0) q.push(i);
while(!q.empty())
{
int x=q.front();
for(int i=h[x];i;i=nxt[i])
{
int y=to[i];
if(du[y]>1) //入度>=2的点即为环上的点
{
du[y]--;
vis[y]=1;
if(du[y]==1) q.push(y);
}
}
}
}
dfs找环
点击查看代码
int dep[N],fa[N],cnt;
void dfs(int u)
{
dep[u]=++cnt;
for(int i=h[u];i;i=nxt[i])
{
int v=to[i];
if(v==fa[u]) continue;
if(dep[v])
{
if(dep[v]<dep[u]) continue;
vis[v]=1;
for(;v!=u;v=fa[v])
{
vis[fa[v]]=1;
}
}
else fa[v]=u,dfs(v);
}
}
有向图
相比于无向图很容易处理，只需要不断dfs即可
点击查看代码
int fa[N];
void dfs(int u)
{
vis[u]=1;
if(vis[fa[x]]) mark=x;
else dfs(fa[x]);
return ;
}
标签：dep,
vis,
int,
void,
dfs,
基环树,
fa
From： https://www.cnblogs.com/zhengchenxi/p/18396802