相当经典的算法。以前都是背模板的，现在打算较深刻地理解一下……

大致思想：遍历到点x时，在栈中的点是有可能与x组成SCC的点。如果x及其子树能够直接访问到的在栈中的DFS序最小的点是x，则x是一个强连通分量在DFS树中的根。每处理完一个根及其子树的信息，就输出此SCC。

对每个节点记录四样东西：DFS序(T)，访问标记，栈标记，节点及其子树能够直接访问到的在栈中的DFS序最小的点的DFS序(L)。访问标记这个可以和DFS序合并，比如DFS序从1开始，那么所有DFS序为0的点就是未访问过的点。

线性时间复杂度的保证在于，每个点最多访问一次，进出栈一次。

假设我们在点x上，初始Lx=Tx。有一条x->y的边，分三类讨论。

1.y未访问，则y一定不在栈中。这说明在DFS树中，y是x的儿子。DFS处理y的信息后Lx=min(Lx,Ly)。

2.y不在栈中，已访问。这说明从y遍历下来的时候没有遍历到x，y已经被分到另一个SCC中了。就是说，虽然x->y，但是y-/>x。x和y不可能在同一个SCC中。Because node y has been visited, nothing should be done。

3.y在栈中，已访问。这说明y->x，x->y，x和y应该在一个SCC中，但是y不一定是SCC的根，怎么办呢？Lx=min(Lx,Ty)即可。

有同学会对3产生疑问：为什么不是Lx=min(Lx,Ly)呢？答案是，这是为了更好地定义，你一定要这么写也可以A题。

由于遍历到x的时候y的子树不一定已遍历完，Ly还没有更新完毕，所以Lx也不能算是节点及其子树能够间接访问到的在栈中的DFS序最小的点的DFS序，于是L的定义就会变得异常奇怪……那样Tarjan就写不粗论文了！！

反正不管怎么样，必定有Lx<=Tx，x必定不是SCC的根，对于y也同样木有影响，所以就这么决定了。

处理完x及其子树后，如果Lx=Tx，则不断弹栈直到弹出x为止，这一段都在且仅在以x为根的SCC中。

#include <stdio.h>
#define maxn 10000
#define maxm 50000
#define ADDEDGE(i,j) stp->next=map[i],(map[i]=stp++)->y=j
struct edge{struct edge*next;int y}*map[maxn],st[maxm],*stp=st;
int n,m,id,t[maxn],l[maxn],s[maxn],k;_Bool in[maxn];
inline getint(){
	int re=0,ch=getchar();_Bool k;
	while(ch!='-'&&(ch<'0'||ch>'9'))if((ch=getchar())<=0)return -1;
	for(k=ch=='-'&&(ch=getchar());ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48;
	return k?-re:re;
}void dfs(i){
	struct edge*p=map[i];in[i]=1;
	for(t[s[k++]=i]=l[i]=++id;p;p=p->next)if(!t[p->y]){
		dfs(p->y);
		if(l[i]>l[p->y])l[i]=l[p->y];
	}else if(in[p->y]&&l[i]>t[p->y])l[i]=t[p->y];
	if(l[i]==t[i]){do{in[s[--k]]=0;printf("%d ",s[k]);}while(s[k]!=i);putchar('\n');}
}main(){
	int i;
	n=getint();m=getint();
	while(m--){
		i=getint()-1;
		ADDEDGE(i,getint()-1);
	}for(i=-1;++i!=n;)if(!t[i])dfs(i);
	return 0;
}

• inline
• block