tarjan 与图的联通性

记录一下各种 tarjan 的模板。

有向图

强联通分量、缩点

void tar(int x) {
	dfn[x] = low[x] = ++ cnt;
	st.emplace(x), ins[x] = 1;
	for (auto y : e[x]) {
		if (!dfn[y]) { tar(y);
			low[x] = min(low[x], low[y]);
		} else if (ins[y]) {
			low[x] = min(low[x], dfn[y]);
		}
	}
	if (dfn[x] == low[x]) {
		++ scc;
		for (int y = 0; y != x;) {
			y = st.top(); st.pop();
			ins[y] = 0, bl[y] = scc;
			vec[scc].emplace_back(y);
		}
	}
}


map<int, map<int, bool>> a;
for (int x = 1; x <= n; x ++) {
	for (auto y : e[x]) {
		int u = bl[x], v = bl[y];
		if (u != v && !a[u][v]) {
			g[u].emplace_back(v);
			g[v].emplace_back(u);
			a[u][v] = a[v][u] = 1;
		}
	}
}

无向图

割点

void tar(int x, int rt) {
	int s = 0;
	dfn[x] = low[x] = ++ cnt;
	for (auto y : e[x]) {
		if (!dfn[y]) { tar(y, rt);
			low[x] = min(low[x], low[y]);
			if (dfn[x] <= low[y]) {
				if (x != rt || ++ s > 1) cut[x] = 1;
			}
		} else low[x] = min(low[x], dfn[y]);
	}
}

边双联通分量

void tar(int x, int fa) {
	dfn[x] = low[x] = ++ cnt;
	st.emplace(x), ins[x] = 1;
	for (auto y : e[x]) if (y != fa) {
		if (!dfn[y]) { tar(y);
			low[x] = min(low[x], low[y]);
		} else if (ins[y]) {
			low[x] = min(low[x], dfn[y]);
		}
	}
	if (dfn[x] == low[x]) {
		++ scc;
		for (int y = 0; y != x;) {
			y = st.top(); st.pop();
			ins[y] = 0, bl[y] = scc;
			vec[scc].emplace_back(y);
		}
	}
}

点双联通分量

void tar(int x, int fa) {
	st.emplace(x);
	dfn[x] = low[x] = ++ cnt;
	for (auto y : e[x]) {
		if (!dfn[y]) { tar(y, x);
			low[x] = min(low[x], low[y]);
			if (dfn[x] <= low[y]) {
				vec[++ dcc] = {x};
				for (int z = -1; z != y;) {
					z = st.top(); st.pop();
					vec[dcc].emplace_back(z);
				}

			}
		} else if (y != fa) {
			low[x] = min(low[x], dfn[y]);
		}
	}
}

还有好多没写，暂时就这些吧（