Tarjan 模板 - 洛谷保存站

SCC 缩点：

```cpp
int n, m, a[N];
vector<int> g[N];
int dfn[N], low[N], ts, stk[N], top;
bool st[N];
int id[N], cnt;

void Tarjan(int u) {
	dfn[u] = low[u] = ++ ts;
	stk[ ++ top] = u;
	st[u] = true;
	
	for (int v : g[u]) {
		if (!dfn[v]) {
			// 树边
			Tarjan(v);
			low[u] = min(low[u], low[v]);
		} else if (st[v]) {
			// 返祖边
			low[u] = min(low[u], dfn[v]);
		}
	}
	
	if (low[u] == dfn[u]) {
		int y;
		++ cnt;
		do {
			y = stk[top -- ];
			st[y] = false;
			id[y] = cnt;
		} while (y != u);
	}
}
```

求割边/边双连通分量：

```cpp
int low[N], dfn[N], ts;
int stk[N], cnt, top;
vector<int> res[N];
bool is_bridge[N];

void dfs(int u, int from) {
	low[u] = dfn[u] = ++ ts;
	stk[ ++ top] = u;
	
	for (int i = h[u]; ~i; i = ne[i]) {
		if (!dfn[e[i]]) {
			dfs(e[i], i);
			low[u] = min(low[u], low[e[i]]);
			if (low[e[i]] > dfn[u]) {
				is_bridge[i] = is_bridge[i ^ 1] = true;
			}
		} else if (i != (from ^ 1)) {
			low[u] = min(low[u], dfn[e[i]]);
		}
	}
	
	if (low[u] == dfn[u]) {
		int y;
		++ cnt;
		do {
			y = stk[top -- ];
			res[cnt].push_back(y);
		} while (y != u);
	}
}
```

求割点/点双连通分量：

```cpp
void dfs(int u, int root) {
	dfn[u] = low[u] = ++ ts;
	stk[ ++ top] = u;
	
	if (u == root && h[u] == -1) {
		ans ++ ;
		res[ans].push_back(u);
		return;
	}
	
	int cnt = 0;
	for (int i = h[u]; ~i; i = ne[i]) {
		int v = e[i];
		if (!dfn[v]) {
			cnt ++ ;
			dfs(v, root);
			low[u] = min(low[u], low[v]);
			
			if (dfn[u] <= low[v]) {
				if (u != root) cut[u] = true;
				
				ans ++ ;
				int y;
				do {
					y = stk[top -- ];
					res[ans].push_back(y);
				} while (y != v);
				res[ans].push_back(u);
			}
		} else {
			low[u] = min(low[u], dfn[v]);
		}
	}
	
	if (u == root && cnt >= 2) cut[u] = true;
}
```

正在渲染内容...