本质

对于一部分问题，可以得出位于同一个边双、点双、强连通以内的节点有共同的性质。Tarjan 提供了一个在 \(O(n+m)\) 的优秀复杂度内把图转化成更特殊问题的方法。

对于有向图，可以获得一个 DAG。这种问题就可以转化成使用 DP、可合并数据结构（如线段树合并、可并堆 \(\dots\)）的求解。
对于无向图，可以获得一棵树。树是很多问题的一个背景，对于较难的题目，可以在这里套上多种算法：树剖、DP等。甚至可以更进一步地利用 DFS 序转化为序列问题~~（不然哪来那么多紫的黑的题）~~。但是越复杂的题，在图论建模上的包装应该就越少，至少还没见过又难建模、建模后又毒瘤的题。只好自己造了一个又水又板但是稍显毒瘤的题（指码量 \(5K\)）。

实现

边双和强连通基本一样，唯一区别就是是否在栈内的 vis 标记。

inline void tarjan(int u,int from){
	dfn[u]=low[u]=++cnt;
	q[++hh]=u;
    vis[u]=1;
	for(int i=h[u];i;i=ne[i]){
		if(i==from) continue;
		int v=e[i];
		if(!dfn[v]) tarjan(v,i^1),low[u]=min(low[u],low[v]);
		else if(vis[v]) low[u]=min(low[u],dfn[v]); 
	}
	if(low[u]==dfn[u]){
		int v;
		++scc_cnt;
		do{
			vis[v=q[hh--]]=0;
		}while(v!=u);
	}
}
for(int i=1;i<=n;++i){
    if(!dfn[i]) tarjan(i,0);
}

点双要把下面的 \(if\) 放到里面去，并且要注意判断单点和自环（边双不判是因为 \(if\) 在外面），且不能弹 \(u\)。

inline void tarjan(int u,int from){
	dfn[u]=low[u]=++cnt;
	q[++hh]=u;
	int tmp=0;
	for(int i=h[u];i;i=ne[i]){
		if(i==from) continue;
		int v=e[i];
		if(!dfn[v]){
			++tmp;
			tarjan(v,i^1),low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]){
				int x;
				++scc_cnt;
				do{
					scc[scc_cnt].push_back(x=q[hh--]);
				}while(x!=v);
				scc[scc_cnt].push_back(u);
			}
		}
		else low[u]=min(low[u],dfn[v]); 
	}
	if(!tmp&&!from) scc[++scc_cnt].push_back(u);
}

注意到，要使用 \(from\) 而不是 \(fa\) 来避免走来时的边。