一般是分为有向图和无向图的：
无向图：
双连通分量：去掉任意一个节点（或一条边）都不会改变这个图的连通性。即不存在割点割边。
所以一般看到跟桥啊割点啊有关的…就想想缩点，入度出度。
无向图缩点Tarjan算法
void tarjan(int u, int fa) { dfn[u] = low[u] = ++tot; instack[u] = 1; sta.push(u); for (int i = head[u]; i; i = e[i].next) { int v = e[i].v; if (v == fa)continue; if (!instack[v]) { tarjan(v, u); low[u] = min(low[u], low[v]); } else { low[u] = min(low[u], dfn[v]); } } if (low[u] == dfn[u] && instack[u]) { ++cnt; while (1) { int x = sta.top(); sta.pop(); instack[x] = 0; belong[x] = cnt; if (x == u)break; } } } int in[maxn]; void solve() { tot = 0; cnt = 0; memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)); memset(instack, 0, sizeof(instack)); memset(in, 0, sizeof(in)); while (sta.size())sta.pop(); tarjan(1, 1); for (int u = 1; u <= n; u++) { for (int i = head[u]; i; i = e[i].next) { int v = e[i].v; if (belong[u] == belong[v])continue; in[belong[u]]++; in[belong[v]]++; } } }
有向图
强连通图：图中任意一对点两两可达。
有向图缩点Tarjan算法
基于dfs，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。
void tarjan(int u) { dfn[u] = low[u] = ++tot; instack[u] = 1; sta.push(u); for (int i = head[u]; i; i = e[i].next) { int v = e[i].v; if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); } else if (instack[v]) { low[u] = min(low[u], dfn[v]); } } if (low[u] == dfn[u]) { int x; ++cnt; while (1) { x = sta.top(); sta.pop(); instack[x] = 0; belong[x] = cnt; if (x == u)break; } } } int in[maxn]; int out[maxn]; void solve() { tot = 0; cnt = 0; memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)); memset(instack, 0, sizeof(instack)); memset(in, 0, sizeof(in)); memset(out, 0, sizeof(out)); while (sta.size())sta.pop(); for (int i = 1; i <= n; i++) { if (!dfn[i])tarjan(i); } for (int u = 1; u <= n; u++) { for (int i = head[u]; i; i = e[i].next) { int v = e[i].v; if (belong[u] != belong[v]) { out[belong[u]]++; in[belong[v]]++; } } } }
原文：https://www.cnblogs.com/amitherblogs/p/12381695.html