电力

tarjan割点 模板题 T3

题目描述

#10103. 「一本通 3.6 练习 4」电力 - 题目 - LibreOJ (loj.ac) 原题来自：CTU Open 2004

求一个无向图图删除一个点之后，连通块最多有多少。

输入格式

多组数据。第一行两个整数 $P,C$ 表示点数和边数。
接下来 $C$ 行每行两个整数 $p1,p2$，表示 $p1$ 与 $p2$ 有边连接，保证无重边。读入以 0 0 结束。

输出格式

输出若干行，表示每组数据的结果。

样例

输入

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

输出

1
2
2

数据范围与提示

$1\le P\le 10000,C\ge 0,0\le p1,p2<P$

思路

下图为两个点双连通分量

若该点在点双连通分量中且不是割点, 则删除后的连通块不会增加。而若是割点, 则删除后连通块会增加。故可以先求出原本连通块数量, 然后枚举所有割点, 计算删除后增加的连通块数量, 加起来即可。

如何判断当前点是不是割点呢？跟边全连通分量类似, 当满足 $dfn[u]\le low[j]$ 时, 说明 $j$ 节点网上最多到达 $u$ 节点, 若 $u$ 节点删除, 就与更上面的节点断连。但当 $u$ 节点是根节点时, 若只有 $j$ 一棵子树, 那么删除后也不会增加连通块, 故当 $u$ 是根节点时, 有两个及以上的子树才会被算作割点。

故代码流程为：

1. tarjan求点双连通分量, 先初始化 $dfn,low$
2. 若当前点 $u$ 的子节点 $j$ 满足 $dfn[u]\le low[j]$ 时, 将当前连通块个数$cnt++$
3. 最后若 $u$ 为根节点, 且 $cnt>1$ 则将 $cnt++$
4. 更新全局变量 $ans$ 即可。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 1e4 + 10, M = 4 * N;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int n, m;
int ans, from;
 
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 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]);
            if (dfn[u] <= low[j])
                cnt++;
        }
        else
            low[u] = min(low[u], dfn[j]);
    }
 
    if (u != from && cnt)
        cnt++;
    ans = max(ans, cnt);
}
 
int main()
{
    while (cin >> n >> m, n || m)
    {
        memset(h, -1, sizeof h);
        memset(dfn, 0, sizeof dfn);
        memset(low, 0, sizeof low);
        idx = timestamp = ans = 0;
 
        while (m--)
        {
            int a, b;
            cin >> a >> b;
            add(a, b), add(b, a);
        }
        int cnt = 0;
        for (from = 0; from < n; from++)
            if (!dfn[from])
            {
                tarjan(from);
                cnt++;
            }
        // cout << cnt << " " << ans << endl;
        cout << cnt + ans - 1 << endl;
    }
    return 0;
}