1.

2.

3.

4.()

5.

6.

7.

<>kk-1

8.11G

Tarjan

1.

Tarjandfnlow

low[u]:=min(low[u],dfn[v])(u,v)vu

low[u]:=min(low[u],low[v])(u,v)vu

low[v]>=dfn[u],uvuvuuuuvvuuuv

?Download sourceCode.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13

void tarjan(int x)
{
 v[x]=1,dfn[x]=low[x]=++num;
 for(int i=head[x];i;i=next[i])
  if(!v[ver[i]])
  {
   tarjan(ver[i]);
   low[x]=min(low[x],low[ver[i]]);
   if(dfn[x]<=low[ver[i]]) v[x]++;
  }
  else low[x]=min(low[x],dfn[ver[i]]);
 if((x==1&&v[x]>2)||(x>1&&v[x]>1)) v[x]=2; else v[x]=1;//v[x]=2
}

 

low[v]>dfn[u],(u,v) (u,v)vdfn[u]low[v]vlow[v]=dfn[v]u(u,v)

 

?Download sourceCode.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void tarjan(int x)
{
 vis[x]=1;
 dfn[x]=low[x]=++num;
 for(int i=head[x];i;i=next[i])
  if(!vis[ver[i]])
  {
   p[ver[i]]=edge[i];//
   tarjan(ver[i]);
   low[x]=min(low[x],low[ver[i]]);
  }
  else if(p[x]!=edge[i])//
   low[x]=min(low[x],dfn[ver[i]]);
 if(p[x]&&low[x]==dfn[x]) f[p[x]]=1;//
}