缩点（Tarjan 算法）
（有向图）强连通分量缩点
强连通分量缩点后的图称为 SCC。以 \(\mathcal O (N + M)\) 的复杂度完成上述全部操作。
性质：缩点后的图拥有拓扑序 \(color_{cnt}, color_{cnt-1},…,1\) ，可以不需再另跑一遍 \(\tt topsort\) ；缩点后的图是一张有向无环图（ \(\tt DAG\) 、拓扑图）。
struct SCC {int n, now, cnt;vector<vector<int>> ver;vector<int> dfn, low, col, S;SCC(int n) : n(n), ver(n + 1), low(n + 1) {dfn.resize(n + 1, -1);col.resize(n + 1, -1);now = cnt = 0;}void add(int x, int y) {ver[x].push_back(y);}void tarjan(int x) {dfn[x] = low[x] = now++;S.push_back(x);for (auto y : ver[x]) {if (dfn[y] == -1) {tarjan(y);low[x] = min(low[x], low[y]);} else if (col[y] == -1) {low[x] = min(low[x], dfn[y]);}}if (dfn[x] == low[x]) {int pre;cnt++;do {pre = S.back();col[pre] = cnt;S.pop_back();} while (pre != x);}}auto work() { // [cnt 新图的顶点数量]for (int i = 1; i <= n; i++) { // 避免图不连通if (dfn[i] == -1) {tarjan(i);}}vector<int> siz(cnt + 1); // siz 每个 scc 中点的数量vector<vector<int>> adj(cnt + 1);for (int i = 1; i <= n; i++) {siz[col[i]]++;for (auto j : ver[i]) {int x = col[i], y = col[j];if (x != y) {adj[x].push_back(y);}}}return {cnt, adj, col, siz};}
};
（无向图）割边缩点
割边缩点后的图称为边双连通图 (E-DCC)，该模板可以在 \(\mathcal O (N + M)\) 复杂度内求解图中全部割边、划分边双（颜色相同的点位于同一个边双连通分量中）。
割边（桥）：将某边 \(e\) 删去后，原图分成两个以上不相连的子图，称 \(e\) 为图的割边。
边双连通：在一张连通的无向图中，对于两个点 \(u\) 和 \(v\)，删去任何一条边（只能删去一条）它们依旧连通，则称 \(u\) 和 \(v\) 边双连通。一个图如果不存在割边，则它是一个边双连通图。
性质补充：对于一个边双，删去任意边后依旧联通；对于边双中的任意两点，一定存在两条不相交的路径连接这两个点（路径上可以有公共点，但是没有公共边）。
struct EDCC {int n, m, now, cnt;vector<vector<array<int, 2>>> ver;vector<int> dfn, low, col, S;set<array<int, 2>> bridge, direct; // 如果不需要，删除这一部分可以得到一些时间上的优化EDCC(int n) : n(n), low(n + 1), ver(n + 1), dfn(n + 1), col(n + 1) {m = now = cnt = 0;}void add(int x, int y) { // 和 scc 相比多了一条连边ver[x].push_back({y, m});ver[y].push_back({x, m++});}void tarjan(int x, int fa) {dfn[x] = low[x] = ++now;S.push_back(x);for (auto &[y, id] : ver[x]) {if (!dfn[y]) {direct.insert({x, y});tarjan(y, id);low[x] = min(low[x], low[y]);if (dfn[x] < low[y]) {bridge.insert({x, y});}} else if (id != fa && dfn[y] < dfn[x]) {direct.insert({x, y});low[x] = min(low[x], dfn[y]);}}if (dfn[x] == low[x]) {int pre;cnt++;do {pre = S.back();col[pre] = cnt;S.pop_back();} while (pre != x);}}auto work() {for (int i = 1; i <= n; i++) { // 避免图不连通if (!dfn[i]) {tarjan(i, 0);}}/*** @param cnt 新图的顶点数量, adj 新图, col 旧图节点对应的新图节点* @param siz 旧图每一个边双中点的数量* @param bridge 全部割边, direct 非割边定向*/vector<int> siz(cnt + 1);vector<vector<int>> adj(cnt + 1);for (int i = 1; i <= n; i++) {siz[col[i]]++;for (auto &[j, id] : ver[i]) {int x = col[i], y = col[j];if (x != y) {adj[x].push_back(y);}}}return tuple{cnt, adj, col, siz};}
};
（无向图）割点缩点
割点缩点后的图称为点双连通图 (V-DCC)，该模板可以在 \(\mathcal O (N + M)\) 复杂度内求解图中全部割点、划分点双（颜色相同的点位于同一个点双连通分量中）。
割点（割顶）：将与某点 \(i\) 连接的所有边删去后，原图分成两个以上不相连的子图，称 \(i\) 为图的割点。
点双连通：在一张连通的无向图中，对于两个点 \(u\) 和 \(v\)，删去任何一个点（只能删去一个，且不能删 \(u\) 和 \(v\)自己）它们依旧连通，则称 \(u\) 和 \(v\) 边双连通。如果一个图不存在割点，那么它是一个点双连通图。
性质补充：每一个割点至少属于两个点双。
struct V_DCC {int n;vector<vector<int>> ver, col;vector<int> dfn, low, S;int now, cnt;vector<bool> point; // 记录是否为割点V_DCC(int n) : n(n) {ver.resize(n + 1);dfn.resize(n + 1);low.resize(n + 1);col.resize(2 * n + 1);point.resize(n + 1);S.clear();cnt = now = 0;}void add(int x, int y) {if (x == y) return; // 手动去除重边ver[x].push_back(y);ver[y].push_back(x);}void tarjan(int x, int root) {low[x] = dfn[x] = ++now;S.push_back(x);if (x == root && !ver[x].size()) { // 特判孤立点++cnt;col[cnt].push_back(x);return;}int flag = 0;for (auto y : ver[x]) {if (!dfn[y]) {tarjan(y, root);low[x] = min(low[x], low[y]);if (dfn[x] <= low[y]) {flag++;if (x != root || flag > 1) {point[x] = true; // 标记为割点}int pre = 0;cnt++;do {pre = S.back();col[cnt].push_back(pre);S.pop_back();} while (pre != y);col[cnt].push_back(x);}} else {low[x] = min(low[x], dfn[y]);}}}pair<int, vector<vector<int>>> rebuild() { // [新图的顶点数量, 新图]work();vector<vector<int>> adj(cnt + 1);for (int i = 1; i <= cnt; i++) {if (!col[i].size()) { // 注意，孤立点也是 V-DCCcontinue;}for (auto j : col[i]) {if (point[j]) { // 如果 j 是割点adj[i].push_back(point[j]);adj[point[j]].push_back(i);}}}return {cnt, adj};}void work() {for (int i = 1; i <= n; ++i) { // 避免图不连通if (!dfn[i]) {tarjan(i, i);}}}
};