图联通问题

割边(Bridge)

模板

vector<pair<int, int> > ans;
vector<int> e[maxn];
void dfs(int u,int fa) {
    dep[u] = dep[fa] + 1;
    for(int v:e[u]) {
        if(v==fa)
            continue;
        if(!dep[v]) {
            dfs(v, u);
            dp[u] += dp[v];
        }
        else {
            if(dep[v]>dep[u]) {
                dp[u]--;//down from u
            }
            else if(dep[v]<dep[u]) {
                dp[u]++;//up form u
            }
        }
    }
    if(!dp[u]&&u!=1){
        brige = 1;
    }
} 

(dp[u])= (#of back-edges going up from u) ​− (# of back-edges going down from u) +(sum dp[v])

如果一个点没有back-edge,那么说明图中存在桥

例题

Bertown roads

CF118E

题意

给一张图n个点m条边，无向边；现在要将这张图变成具有m条单向边的图，并且保证任意两点之间相互到达

思路

DFS树，并且统计每个点的back-edge个数，如果为0则代表它与它的parent会形成割桥，则输出0即可

链接 : https://xlorpaste.cn/28k1dx