基础知识

无向图的割点与桥
给定无向图$G=(V,E)$:
若对于$x\in V$,从图中删去节点$x$以及所有与$x$关联的边后，$G$分裂成两个不连通的子图，则称$x$是$G$的割点。
若对于$e\in E$,从图中删去边$e$之后，$G$分裂成两个不相连的子图，则称$e$为$G$的桥或割边。

割边的判定
无向边$(x,y)$是桥，当且仅当搜索树上存在$x$的一个子节点$y$,满足：
$$dfn[x]<low[y]$$
在无向图中不存在横插边，所以说如果满足以上条件，要么说明以$y$为根的子树只存在树边，要么说明下图中存在类似于红色这样的后向边，即无法通过其他路径到达$x$或以上的部分，即把$(x,y)$删掉之后，$subtree(y)$会形成一个封闭的部分。如果不满足条件，则存在类似于绿色这样的边，即可以到达$x$或之前的点。

割点的判定
若$x$不是搜索树的根节点，则$x$是割点当且仅当搜索树上存在$x$的一个子节点$y$,满足：
$$dfn[x]\le low[w]$$
特别的，若$x$是搜索树的根节点，则$x$是割点当且仅当搜索树存在两个子节点$y1$,$y2$满足上面的条件。

无向图的双连通分量
若一张无向图不存在割点，则称它为"点双连通图"。若一张无向连通图不存在桥，则称它为"边双连通图"。

无向图的极大点双连通图被称为“点双连通分量”，简记为"v-DCC"。无向图的极大边双连通子图被称为“边双连通分量”,简记为"e_DCC"。两者统称为边双连通分量，简记为"DCC”。

冗余路径

为了从 $F$ 个草场中的一个走到另一个，奶牛们有时不得不路过一些她们讨厌的可怕的树。

奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的路径，这样她们就有多一些选择。

每对草场之间已经有至少一条路径。

给出所有 $R$ 条双向路的描述，每条路连接了两个不同的草场，请计算最少的新建道路的数量，路径由若干道路首尾相连而成。

两条路径相互分离，是指两条路径没有一条重合的道路。

但是，两条分离的路径上可以有一些相同的草场。

可能有不止一条道路直接连接同一对草场，尽管如此，你仍可以在它们之间再建一条道路，作为另一条不同的道路。

输入格式
第 $1$ 行输入 $F$ 和 $R$。

接下来 $R$ 行，每行输入两个整数，表示两个草场，它们之间有一条道路。

输出格式
输出一个整数，表示最少的需要新建的道路数。

数据范围
$1\le F\le 5000,F-1\le R\le 10000$

输入样例：

7 7
1 2
2 3
3 4
2 5
4 5
5 6
5 7

输出样例：

2

结论：一个边的双连通分量 <=> 任何两个点之间至少存在两个不相交路径
充分性: 对于每两个点都有互相分离的路径的话，则必然为强连通分量
反证 假设有桥(非双连通)$x,y$必然经过中间的桥 则只x→y的路径必在桥上相交
必要性：图是一个边双连通分量 <=> 不包含桥,则一定对任意两点$x,y$之间至少存在两条互相分离(不相交)的路径
反证:假设存在两条相交路径
那么$x\to y$中间必然有桥

所以，本题要求添加最少条边使得任何两个点之间至少存在两个不相交路径，也即给无向图加边，使得无向图没有桥（即变成边双连通分量），最小化加边数。

因为边双连通分量本来就没有桥，所以我们考虑对整个图求一遍边双连通分量（使用 tarjan 算法），然后将边双连通分量缩为一个点考虑。那么缩完点后得到的图一定是一棵树（因为图中不可能存在环）。

先给出结论：
所加的边数至少为$\lceil \frac{cnt}{2}\rceil$， 为叶结点个数），而这恰好就是答案。

下面，我们要证明的是：
1.加边数至少为 $\lceil \frac{cnt}{2}\rceil$
2. 给连通的无向图加$\lceil \frac{cnt}{2}\rceil$ 为叶结点个数）条边即可保证所得的图为边双连通分量

先证明 1：因为对于一个叶子节点 $t$ ，如果把它与父节点相连的边割去会让它成为独立点，所以每个叶子节点都需要向其它点连一条边，因此加边数至少为 $\lceil \frac{cnt}{2}\rceil$ 。

下证 2：
当图的点数 $V$ 为 2 时，两个点都是叶节点，结论成立。

考虑 $V⩾2$ 的情况：

我们一定可以找到一个度数大于 1, 的点，我们将它作为根节点 $root$ ，直观的构造方法是：
叶子节点取 $\lfloor \frac{cnt}{2}\rfloor$ 个点与另外 $\lfloor \frac{cnt}{2}\rfloor$ 个一一相连，如果多出一个点则向根节点连接。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 5010, M = 20010;
int h[N], e[M], ne[M], tot;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool is_bridge[M];
int id[N], dcc_cnt;
int d[N];
int n, m;
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] = 1;
        }
        else if (i != (from ^ 1))
            low[u] = min(low[u], dfn[j]);
    }
    if (low[u] == dfn[u])
    {
        int y;
        dcc_cnt ++ ;
        do{
            y = stk[top -- ];
            id[y] = dcc_cnt;
        }while (y != u);
    }
}
void add(int a, int b)
{
    e[tot] = b, ne[tot] = h[a], h[a] = tot ++ ;
}
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 1; i <= m; i ++ )
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    tarjan(1, -1);
    for (int i = 0; i < tot; 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;
}

电力

给定一个由 $n$ 个点 $m$ 条边构成的无向图，请你求出该图删除一个点之后，连通块最多有多少。

输入格式
输入包含多组数据。
每组数据第一行包含两个整数 $n,m$。

接下来 $m$ 行，每行包含两个整数 $a,b$，表示 $a,b$ 两点之间有边连接。

数据保证无重边。

点的编号从 $0$ 到 $n-1$。

读入以一行 $00$ 结束。

输出格式
每组数据输出一个结果，占一行，表示连通块的最大数量。

数据范围
$1\le n\le 10000,0\le m\le 15000,0\le a,b<n$

输入样例：

3 3
0 1
0 2
2 1
4 2
0 1
2 3
3 1
1 0
0 0

输出样例：

1
2
2

（1）统计一下所有连通块的个数（结果为$cnt$）；

（2）枚举从哪个块中删，然后再枚举这个块中删除哪个点，会得到删除点之后形成块的数量，去最大值，记为$ans$。最终的答案就是$ans+cnt-1$。

我们需要考虑删除哪个点？答案是我们应该删除每个连通块中的割点，因为根据割点定义，只有删除割点才能使连通块的数量增加。对于每个连通块而言，如果$u$是割点，假设$u$存在2个孩子，此时还需要判断$u$是否为这个图的根节点（即遍历该连通块时第一个遍历到的节点），如果是根节点，则删去$u$之后能形成2个连通块，如果$u$不是根节点，则删去$u$之后能形成3个连通块。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 10010, M = 30010;
int h[N], e[M], ne[M], tot;
int dfn[N], low[N], timestamp;
int ans;
int root;
int n, m;
void add(int a, int b)
{
    e[tot] = b, ne[tot] = h[a], h[a] = tot ++ ;
}
void tarjan(int u)
{
    int cnt = 0;
    dfn[u] = low[u] = ++ timestamp;
    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 (low[j] >= dfn[u]) cnt ++ ;
        }
        else low[u] = min(low[u], dfn[j]);
    }
    if (u != root) cnt ++ ;
    ans = max(ans, cnt);
}
int main()
{
    while (cin >> n >> m, n || m)
    {
        memset(dfn, 0, sizeof dfn);
        memset(h, -1, sizeof h);
        tot = timestamp = 0;
        for (int i = 1; i <= m; i ++ )
        {
            int a, b;
            cin >> a >> b;
            add(a, b), add(b, a);
        }
        ans = 0;
        int cnt = 0;
        for (root = 0; root < n; root ++ )
        {
            if (dfn[root]) continue;
            tarjan(root);
            cnt ++ ;
        }
        cout << cnt + ans - 1 << endl; 
    }
    return 0;
}

[HNOI2012] 矿场搭建

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。

请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。

输入格式

输入文件有若干组数据。

每组数据的第一行是一个正整数 $N(N\le 500)$，表示工地的隧道数。

接下来的 $N$ 行每行是用空格隔开的两个整数 $S$ 和 $T$，表示挖煤点 $S$ 与挖煤点 $T$ 由隧道直接连接。

输入数据以 $0$ 结尾。

输出格式

对于每组数据，输出一行。

第 $i$ 行组数据以 $\text{Case i: }$ 开始（注意大小写，$\text{Case}$ 与 $\text{i}$ 之间有空格，$\text{i}$ 与 $\text{:}$ 之间无空格，$\text{:}$ 之后有空格）。

其后是用空格隔开的两个正整数，第一个正整数表示对于第 $i$ 组输入数据至少需要设置几个救援出口，第二个正整数表示对于第 $i$ 组输入数据不同最少救援出口的设置方案总数。

输入数据保证答案小于 $2^{64}$。输出格式参照以下输入输出样例。

输入输出样例 #1

输入 #1

9
1 3
4 1
3 5
1 2
2 6
1 5
6 3
1 6
3 2
6
1 2
1 3
2 4
2 5
3 6
3 7
0

输出 #1

Case 1: 2 4
Case 2: 4 1

说明/提示

样例解释

• Case 1 的四组解分别是 $(2,4)$，$(3,4)$，$(4,5)$，$(4,6)$；
• Case 2 的一组解为 $(4,5,6,7)$。

数据范围及约定

对于每组数据，设 $m$ 为各组 $S,T$ 中最大值，则有：

• $1\le m\le 10^3$；
• 各组 $S,T$ 构成的集合 $V=[1,m]\cap \mathbb{Z}$。
• $V$ 中任意两点连通。

求$v-dcc$，缩点，得到一棵树。
1.对于每一个孤立的节点，如果这个节点的大小为1，则出口数$res++$；反之，$res+=2$,情况总数$cnt\ast =C_{sz}^2$。
因为对于一个孤立的点他自己就是一个点双连通分量，我们在里面防止两个点，即使其中一个出口塌陷，其余所有点都能到达另一个出口。
2.对于度为1的节点，在里面非割点位置可以设置一个节点即$res++$，$cnt\ast =(sz-1)$，这样，如果割点塌陷，内部所有点也都可以通过这个出口出去；如果出口塌陷，那么所有点也能通过割点去到其他连通块，找到其他的出口。
3.对于度为2的节点，可以不设置任何节点，因为不管里面哪一个点塌陷，都可以通过割点去到其他连通块找到其他出口。

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
typedef unsigned long long ULL;
const int N = 1010, M = 1010;
int h[N], e[M], ne[M], tot;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool cut[N];
int dcc_cnt;
int root;
vector<int> dcc[N];
int n, m;
void add(int a, int b)
{
    e[tot] = b, ne[tot] = h[a], h[a] = tot ++ ;
}
void tarjan(int u)
{
    low[u] = dfn[u] = ++timestamp;
    stk[++top] = u;
    // 1 u是孤立点-自称一个dcc
    if(u==root && h[u]==-1)//u是根节点且没有邻边
    {
        dcc_cnt++;
        dcc[dcc_cnt].push_back(u);
        return;
    }
    // 2 u不孤立
    int cnt = 0;
    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]);
            // 看j是不是能连到比u还高的地方
            if(dfn[u]<=low[j])//j最高比u高度低 说明j是u一个新的分支(如果把u删掉 多一个j连通块)
            {
                cnt++;
                // 判断u是否割点 如果不是根节点-只要有一个分支他就是割点 || 如果是根节点 需要有两个分支才是割点
                //    root            /
                //    / \          非root(自带上面一个边,所以只要一个下分支)
                //                   /
                if(u!=root||cnt>1)cut[u] = true;
                ++dcc_cnt;
                int y;
                do{
                    y = stk[top--];
                    dcc[dcc_cnt].push_back(y);
                }while(y!=j);//注意弹出栈不是弹到u为止 而是弹到j为止(u仍保留在stk中)
                // 🔺 开新分支 == u一定和新分支j组成一个dcc 也和旧连通块组成dcc
                // 那么当前最高点u还要被用在更高的包含u的旧连通块
                // 所以如果这个时候出栈了 回溯到比u高的点的时候 u就加不进旧连通块里
                dcc[dcc_cnt].push_back(u);
            }
        }
        else low[u] = min(low[u],dfn[j]);
    }
}

int main()
{
   int T = 1;
    while(cin >> m,m)
    {
        for(int i=1;i<=dcc_cnt;i++)dcc[i].clear();
        tot = n = timestamp = top = dcc_cnt = 0;
        memset(h,-1,sizeof h);
        memset(dfn,0,sizeof dfn);
        memset(cut,0,sizeof cut);
        while(m--)
        {
            int a,b;
            cin >> a >> b;
            n = max(n,b),n = max(n,a);//第二个n=漏了
            add(a,b),add(b,a);
        }

        for (root = 1; root <= n; root ++ )
            if (!dfn[root])
                tarjan(root);

        int res = 0;
        ULL num = 1;
        for(int i = 1;i<=dcc_cnt;i++)
        {
            int cnt = 0;
            for(int j= 0;j<dcc[i].size();j++)//j< 写成了i<
            {
                if(cut[dcc[i][j]])
                    cnt++;
            }
            // 无割点
            if(cnt == 0)//cnt写成了cut
            {
                if(dcc[i].size()>1)res+=2,num*=dcc[i].size()*(dcc[i].size()-1)/2;
                else res++;
            }
            else if(cnt==1)res++,num*=dcc[i].size()-1;
        }
        printf("Case %d: %d %llu\n", T ++, res, num);
    }
    return 0;
}