【模板】——tarjan （附：缩点）

tarjan算法的模板

void tarjan(int u)
{
    dfn[u]=low[u]=++js;//dfn即时间戳，js即计数，low[u]即与u点形成强联通的第一个点
    st[++top]=u;
    for(int i=head[u];i;i=mapp[i].next;)
    {
        int v=mapp[i].value;
        if(!dfn[v])//未染色的点（白点）
        {
            tarjan(v);
            low[u]=min(low[v],low[u]);
        }
        else if(!lt[u])//已入栈，但未出栈的点（灰点）
            low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u])//记录各个强联通的编号
    {
        lt[u]=++lts;//lt[u]即u点属于的强联通的编号；lts即联通数（强联通的编号）
        while(st[top]!=u)
            lt[st[top--]]=lts;
        lts--;
    }
}

附：缩点（该段代码直接插入到主函数调用tarjan算法之后即可）

for(int i=1;i<=n;i++)//缩点并执行操作
    for(int j=head[i];j;j=mapp[j].next)
	{
	    int v=mapp[j].value;
	    /*
            if(lt[i]!=lt[v])//记录缩完点后每一个点的入读和初度
    		{
    		    out[lt[i]]++;
		    in[lt[v]]++;
		}
            */
            /*
            add(lt[u],lt[v]);//重新建一个图（有向无环）
            */
	}