无向图的双连通分量

AcWing 395. 冗余路径

题目

https://www.acwing.com/problem/content/397/ 为了从 F 个草场中的一个走到另一个，奶牛们有时不得不路过一些她们讨厌的可怕的树。 奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的路径，这样她们就有多一些选择。 每对草场之间已经有至少一条路径。 给出所有 R 条双向路的描述，每条路连接了两个不同的草场，请计算最少的新建道路的数量，路径由若干道路首尾相连而成。 两条路径相互分离，是指两条路径没有一条重合的道路。 但是，两条分离的路径上可以有一些相同的草场。 对于同一对草场之间，可能已经有两条不同的道路，你也可以在它们之间再建一条道路，作为另一条不同的道路。

思路

割点： 对于一个连通图中的点 x，假如删去这个点以及与所有 x 相连的边之后图不连通，那么称 x 为该图的割点。

• 每个割点至少属于两个连通分量

边双连通：在一张连通的无向图中，对于两个点 u和v ，如果无论删去哪条边（只能删去一条）都不能使它们不连通，我们就说 u和 v 边双连通。 点双连通：在一张连通的无向图中，对于两个点 u和v ，如果无论删去哪个点（只能删去一个，且不能删 和 自己）都不能使它们不连通，我们就说 u和v 点双连通。 桥：在图论中，一条边被称为“桥”代表这条边一旦被删除，这张图的连通块数量会增加。

• 树里的每条边都是桥

本题题意： 给定一个连通的无向图让你进行加边操作，要求每一对点之间都至少有两条相互分离的路径，求最小的加边数。即给连通的无向图加边，使得无向图没有桥（即变成边双连通分量），最小化加边数。 做法： 对整个图求一遍边双连通分量（tarjan算法），然后将边双连通分量缩为一个点考虑。那么缩完点后得到的图一定是一棵树。

求解加多少条边可以变成双连通分量?

所加边数至少为$(cnt+1)/2$cnt为叶子节点 边的双连通分量e-dcc：极大的不包含桥的连通块 点的双连通分量v-dcc：极大的不包含割点的连通块

如何求桥？

等价于：dfn[x]<low[y] 表示y无论如何往上走不到x

如何判断当前节点是双联通分量的最高点?

判断到某一个点y之后他的dnt[y]==low[y]那么就说明x最高遍历得到的节点就是他自己，说明只可能有一条桥边连接这个点。

代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N=5010,M=20010;
int n,m;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int stk[N],top;
int id[N],dcc_cnt;
bool is_bridge[M];
int d[N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void tarjan(int u,int from)
{
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u;
    
    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])
                is_bridge[i]=is_bridge[i^1]=true;
        }else if (i!=(from^1))
            low[u]= min(low[u],dfn[j]);
    }
    if (dfn[u]==low[u])
    {
        ++dcc_cnt;
        int y;
        do {
            y=stk[top--];
            id[y]=dcc_cnt;
        } while (y!=u);
    }
}

int main() {
    cin>>n>>m;
    memset(h,-1, sizeof h);
    while (m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b), add(b,a);
    }
    tarjan(1,-1);
    for(int i=0;i<idx;i++)
        if (is_bridge[i])
            d[id[e[i]]]++;
    int cnt=0;
    for(int i=1;i<=dcc_cnt;i++)
        if (d[i]==1)
            cnt++;
    cout<<(cnt+1)/2;
    return 0;
}

AcWing 1183. 电力

题目

https://www.acwing.com/problem/content/1185/ 给定一个由 n 个点 m 条边构成的无向图，请你求出该图删除一个点之后，连通块最多有多少。

思路

求割点： 对于一条边u-j , 如果$(low[j]>=dfn[u])$那么就说明从j节点不能到达u节点，那么就说明u节点是一个割点 步骤：

• 用tarjan算法把每一个连通块求出来
• 对于每一个连通块，如果$dfn[u]<=low[j]$,删除u点，会使得j所在的连通块成为一个新的连通块
• 记录下有多少个j，特判如果u不是连通块的根节点，会多出一个连通块

简单来说：求割点，没有割点答案就是连通块个数，否则就是删去割点后连通块的个数

代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N=10010,M=30010;
int n,m;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int root;//每个连通块的根节点
int ans;//记录每个连通块去掉一个点形成的连通块数目的最大值


void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void tarjan(int u)
{
    dfn[u]=low[u]=++timestamp;
    int s=0;//如果当前点u是割点的话，去掉该点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]) s++;// 说明u是可能是割点, u存在一棵子树(删除割点u)
        }else low[u]= min(low[u],dfn[j]);
    }
    if (u!=root) s++;//如果不是根节点最后还要加上父节点部分1
    ans= max(ans,s);
}

int main() {
    while (cin>>n>>m,n||m)
    {
        memset(dfn,0,sizeof dfn);
        memset(h,-1,sizeof h);
        idx=timestamp=0;
        while (m--)
        {
            int a,b;
            cin>>a>>b;
            add(a,b), add(b,a);
        }
        ans=0; //记录删除不同割点之后形成的连通块的最大值
        int cnt=0; // 记录连通块的数目
        for(root=0;root<n;root++) //每次将其中联通块遍历，用tarjan
            if (!dfn[root]){
                cnt++;
                tarjan(root);
            }
        cout<<cnt+ans-1<<endl;
    }
    return 0;
}