概念:

桥:无向图中删去一条边使得图不再联通,则这条边称为桥

割点:无向图中删去一个点使得图不再联通,则这个点称为割点

算法:

运用到tarjan算法

关于tarjan算法: 

求桥: 对于一条边 u -> v, 如果它是树边且low[v] > dfn[u], 则这条边为桥, 因为删去了这条边, v无法到达u以及u以上的点

求割点:对于一个点u, 如果它是根节点,且子树个数大于等于2, 则u是割点, 因为删去这个点后它的子树之间不能互相到达

　　　　　　　　　 如果它不是根节点, 假设它有一个儿子为v, 如果low[v] >= dfn[u], 则u是割点, 因为删去u后v无法到达u以上的点

模板:

const int N = 1e5 + 5;vector
     
      
       > g[N];int low[N], dfn[N], tot = 0;pair
       
         fa[N];bool is_cut[N], is_bridge[N];void tarjan(int u, pair
        
          o) {    fa[u] = o;    dfn[u] = low[u] = ++tot;    for (pair
         
           p : g[u]) {        int v = p.fi;        if(!dfn[v]) {            tarjan(v, {u, p.se});            low[u] = min(low[u], low[v]);        }        else if(v != o.fi) low[u] = min(low[u], dfn[v]);    }}void solve(int n) {    tarjan(1, {
   1, 1});    //求割点    int son = 0;    for (int v = 2; v <= n; v++) {        if(fa[v].fi == 1) son++;        else {            int u = fa[v].fi;            if(low[v] >= dfn[u]) is_cut[u] = true;        }    }    if(son >= 2) is_cut[1] = true;    //求桥    for (int v = 2; v <= n; v++) {        int u = fa[v].fi;        if(low[v] > dfn[u]) is_bridge[fa[v].se] = true;    }}
         
        
       
      
     

 概念:

边双连通分量:不存在桥的无向图为边双连通图, 极大边双连通图为边双连通分量

思路:边双联通分量与强联通分量类似,一个无向图, 一个有向图

模板:

const int N = 1e5 + 5;vector
     
       g[N];vector
      
        bcc[N];bool vis[N];int low[N], dfn[N], stk[N], tot = 0, top = 0, cnt = 0;void tarjan(int u, int fa) {    low[u] = dfn[u] = ++tot;    stk[++top] = u;    vis[u] = true;    for (int v : g[u]) {        if(v == fa) continue;        if(!dfn[v]) {            tarjan(v, u);            low[u] = min(low[u], low[v]);        }        else if(vis[v]) low[u] = min(low[u], dfn[v]);    }    if(low[u] == dfn[u]) {        ++cnt;        while(stk[top] != u) vis[stk[top]] = false, bcc[cnt].pb(stk[top--]);        vis[stk[top]] = false, bcc[cnt].pb(stk[top--]);    }}
      
     

点双连通分量:不存在割点的无向图为点双连通图, 极大点双连通图为点双连通分量

模板:

const int N = 1e5 + 5;vector
     
       g[N];vector
      
       
        > bcc[N];int low[N], dfn[N], tot = 0, top = 0, cnt = 0;pair
        
          stk[N];void tarjan(int u, int fa) {    low[u] = dfn[u] = ++tot;    for (int v : g[u]) {        pair
         
           e = {u, v};        if(!dfn[v]) {            stk[++top] = e;            tarjan(v, u);            low[u] = min(low[u], low[v]);            if(low[v] >= dfn[u]) {                cnt++;                while(stk[top] != e) {                    bcc[cnt].push_back(stk[top--]);                }                bcc[cnt].push_back(stk[top--]);            }        }        else if(v != fa ) {            if(dfn[v] < dfn[u]) stk[++top] = e, low[u] = min(low[u], dfn[v]);        }    }}