Tarjan

模板

缩点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void tarjan(int u){
	dfn[u]=low[u]=++num;
	stak[++top]=u;vis[u]=1;
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(vis[v]) low[u]=min(low[u],low[v]);
	}
	if(dfn[u]==low[u]){
		tot++;
		while(stak[top]!=u){
			vis[stak[top]]=0;
			color[stak[top]]=tot;
			top--;
		}
		top--;
		vis[u]=0;
		color[u]=tot;
	}
}

Tarjan技巧

1.dfn可以作为mark一样的作用记录节点是否被访问
2.缩点更新low[u]的时候也可也写成low[u]=min(low[u],dfn[v])

题型