常州集训Day1

刚来就从S转到J（第一次出省集训）下午又转回来。
S组今天主要讲连通性问题，主要是强连通分量、割边、割点、缩点这些。主要用Tarjan算法来实现。
代码如下（无向图）：

void tarjan(int x,int eid){
    dfn[x]=low[x]=++num;
    for(int i=head[x];i;i=nxt[i]){
        if(i==eid^1) continue;
        int y=ver[i];
        if(dfn[y]){
            tarjan(y,i);
            low[x]=min(low[x],low[y]);
            if(low[y]>dfn[x]) cut[i]=cut[i^1]=true;
        }
        else low[x]=min(low[x],dfn[y]);
    }
}

（比较抽象，但大概懂了）
有向图可能会出现回溯过的点仍需要使用的情况，可以利用栈记录访问过的点，流程如下：
1.dfs，第一次访问x把x入栈，low[x]=dfn[x]
2.扫描(x,y) （1）y没被访问，是树枝边，递归访问y，y回溯后，更新low[x]
（2）y被访问，且y在栈中，更新low[x]=min(low[x],dfn[y])
3.x回溯前，判断是否有low[x]>dfn[x]，若有，不断弹栈直至x出栈，
这些所有点构成强连通分量
自己画图理解