正常的求环的tarjan
点击查看代码
int tp,s[N],in_stack[N];
int dfn[N],low[N],dfncnt;
int scc[N],sc,sz[N];
void tarjan(int u)
{
dfn[u]=low[u]=++dfncnt;
s[++tp]=u;
in_stack[u]=1;
for(int i=h[u];i;i=nxt[i])
{
int v=to[i];
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(in_stack[v])
{
low[u]=min(dfn[v],low[u]);
}
}
if(dfn[u]==low[u])
{
sc++;
while(s[tp]!=u)
{
scc[s[tp]]=sc;
in_stack[s[tp]]=0;
sz[sc]++;
tp--;
}
scc[s[tp]]=sc;
in_stack[s[tp]]=0;
sz[sc]++;
tp--;
}
}
圆方树
点击查看代码
#include"bits/stdc++.h"
using namespace std;
const int N=1e6;
int n,m;
int f[N][2];
vector<int> tr[N<<1];
int cnt;
int h[N],to[N],nxt[N],tot;
void add(int x,int y)
{
to[++tot]=y;
nxt[tot]=h[x];
h[x]=tot;
}
int low[N],dfn[N],dfncnt;
int s[N],tp;
void tarjan(int u)
{
low[u]=dfn[u]=++dfncnt;
s[++tp]=u;
for(int i=h[u];i;i=nxt[i])
{
int v=to[i];
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
if(low[v]==dfn[u])
{
++cnt;
for(int x=0;x!=v;--tp)
{
x=s[tp];
tr[cnt].push_back(x);
tr[x].push_back(cnt);
}
tr[cnt].push_back(u);
tr[u].push_back(cnt);
}
else low[u]=min(low[u],dfn[v]);
if(low[v]>dfn[u])
{
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
cnt=n;
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i])
{
tarjan(i),--tp;
}
}
return 0;
}