无向图的割边判断法则

首先无向图中不存在横叉边
subtree(i): 以i为根节点的子树。 dfn[x] : x节点的时间戳。 low[y]：表示y的追溯值
无向图（x, y）为桥，当且仅当搜索树上存在x的一个子节点满足：
dfn[x] < low[y],那么y无论如何走走不到x或者x的祖宗节点，那么把这条边删了，相当于形成了两个封闭环境，那么（x,y）就是割边即桥。
由于是无向图因此如果是从x到y的边，那么就不能用从y到x的边来更新low[y],但是如果 存在重边的话因为这两点可以通过不同的路径到达，那么就可以用dfn[x]来更新low[y];

void tarjan(int u, int in_edge) // in_edge为u的父节点到u的边的编号 
{
    dfn[u] = low[u] = ++ timestamp; // 时间戳

    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!dfn[j) // 如果没有遍历过这个点
        {
            tarjan(j, i);
            low[u] = min(low[u], low[j]);
            if(dfn[u] < low[j]) //满足割边要求
            {
                in_bridge[i] = in_bridge[i ^ 1] = true; //因为是双向边，两条边都标记一下
            }
        }
        else if(i != in_dege^1)low[u] = min(low[u], dfn[j]); // 如果这条边不是父节点到子节点的逆边
    }
}

割点的判断法则
若x不是搜索树的根节点（深度优先遍历的起点），则x是割带你当且仅当搜索树上存在x的一个子节点y满足
dfn[x] <= low[y];
若x是搜索树的根节点，则当且仅当搜索树上存在至少两个点y1, y2满足上述条件。
这里由于去等号了，所以不需要在判断父节点和重边问题。

void tarjan(int u)
{
    dfn[u] = low[u] = ++timestamp; // 时间戳
    int cnt = 0; // 判断u节点 存在几个满足上述的子节点
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!dfn[j]) // 没有遍历过
        {
            tarjan(j);
            low[u] = min(low[u], low[j]); // 更新时间戳
            if(dfn[u] <= low[j]) //满足条件
            {
                cnt ++;
                if(u != root || cnt > 1)in_val[u] = true; // 如果u不是根节点或者满足条件的子节点大于1 了标记
            }
        }
        else low[u] = min(low[u], dfn[j]); //跟新low[u]
    }
}

无向图的双联通分量
包括边的双联通分量e-DCC和点的双联通分量v-DCC
- 点的双联通分量满足条件
1图中的定点数不超过2
2图中任意两点都同时包含在至少一个简单环中。简单环就是不自交的环。
- 边的双联通分量满足条件
1 当且仅当任意一条边都包含在至少一个环中
e-DCC求法
先用tarjan算法标记所有的桥边，再做一遍dfs，遍历过程中不访问桥边，划分出每个联通块.
id[x] 表示节点x所属的e-DCC编号

void dfs(int u)
{
    id[x] = dcc_cnt; // 节点编号
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(id[j] || in_bridge[j])continue; // 如果子节点已经被遍历过或者说子节点和父节点之间的边为桥
        dfs(j);
    }
}

e-DCC缩点操作
把每个e-DCC看成一个点，把桥边（x, y） 当成id[x] 与 id[y] 的无向边，会产生一棵树（若原图为非联通图，则产生生成森林）。

for(int i = 0; i < idx; i ++)//枚举每条边
{
    int a = e[i ^ 1], b = e[i];//把连接边的两个节点编号抠出来
    if(id[a] == id[b]) continue;//判断两个点是否属于同一个e-DCC，属于的话pass
    add(a, b);// 把两个节点练一条边。
}

点的双连通分量v-dcc的求法
首先要明确一点，每个割点至少存在与两个或两个以上的v-dcc中
除了孤立点外，v-dcc分量的大小至少为2
如何找出所有的v-dcc
1) 当一个节点第一次被访问时，把该节点入栈
2）当判定割点的条件dfn[x] <= low[y] 成立时，无论x是否为根，都要
1.从栈顶不断弹出节点，知道节点y弹出。
2 要把刚刚弹出的所有点与割点x一起 组成一个v-dcc

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp; // 时间戳
    stk[++ top] = u; // 把当前点放到栈中
    if(u == root && h[u] == -1) //如果为孤立点单独处理
    {
        ++ dcc_cnt; // v-dcc编号
        dcc[dcc_cnt].push_back(u);
        return ;
    }
    int cnt = 0; // 割点下面有几个v-dcc
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = ne[i];
        if(!df[j])//没有遍历过的话
        {
            tarjan(j);
            low[u] = min(low[u], low[j]); // 更新low[u]
            if(dfn[u] <= low[j]) //符合割点判断条件
            {
                ++ cnt;
                if(u != root || cnt > 1) cnt[u] = true; // 如果是割点那么标记一下
                int y;
                ++ dcc_cnt; // v-dcc编号
                do 
                {
                    y = stk[top --];// v-dcc的成员节点
                    dcc[dcc_cnt].push_back(y);
                }while(y != j);
                dcc[dcc_cnt].push_back(u);
            }
            else low[u] = min(low[u], dfn[j]); // 最后把x要放到v-dcc中
        }
    }
}

v-dcc的缩点
v-dcc的建图和e_dcc、scc不太一样
由于一个割点可能属于多个v-dcc,设图中有p个割点和t个v-dcc。建图的话就是用每个v-dcc的编号向它所包含的每个割点连一条无向边，因此节点数目可能为2*N个。

for(int i = 1; i <= n; i ++)
    if(cnt[i])new[i] = ++ idx; // 先把每个割点赋予一个新的编号
for(int i = 1; i <= dcc_cnt; i ++)// 枚举每一个v-dcc如果存在割点就向割点的新编连一条无向边
    for(int j = 0; j < dcc[i].size(); j ++)
    {
        int k = dcc[i][j];
        if(cnt[k])add(i, new[k]), add(new[k], i); 
    }

总结：强联通分量缩点后变成拓扑图。
双联通分量缩点后变成树。
一个点即是e-dcc也是v-dcc
两个点是v-dcc但不是e-dcc