Luobuyu's Blog

0%

P3388 【模板】割点（割顶）

发表于 分类于 热度： ℃ 评论：
本文字数： 1.8k 阅读时长 ≈ 2 分钟
割点模板题。

P3388.【模板】割点（割顶）

题目描述：

给出一个 $n$ 个点，$m$ 条边的无向图，求图的割点。

数据范围：

$1\le n \le 2\times 10^4,1\le m \le 10^5$

点编号从 $1$ 开始，tarjan图不一定连通

题解：

割点模板，需要判断是否是树根，树根需要看子树的数量，子树数量大于 $1$ 则树根是割点，其余的需要判断 $low[v] \ge dfn[u]$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 2e4 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
vector<int> g[maxn];
bool ans[maxn];
int dfn[maxn], low[maxn], dfn_clock = 0;
void tarjan(int u, int fa, bool isRoot)
{
    low[u] = dfn[u] = ++dfn_clock;
    int child_cnt = 0;
    for (int i = 0; i < g[u].size(); ++i)
    {
        int v = g[u][i];
        if (!dfn[v])
        {
            tarjan(v, u, false);
            low[u] = min(low[u], low[v]);
            if (!isRoot && low[v] >= dfn[u])
                ans[u] = true;
            ++child_cnt;
        }
        else
        {
            if (v != fa)
                low[u] = min(low[u], dfn[v]);
        }
    }
    if (isRoot && child_cnt >= 2)
        ans[u] = true;
}
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    read(n, m);
    for (int i = 1, u, v; i <= m; ++i)
    {
        read(u, v);
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    for (int i = 1; i <= n; ++i)
    {
        if (!dfn[i])
            tarjan(i, -1, true);
    }
    int cnt = 0;
    for (int i = 1; i <= n; ++i)
    {
        cnt += ans[i];
    }
    cout << cnt << endl;
    for (int i = 1; i <= n; ++i)
    {
        if (ans[i])
            cout << i << " ";
    }
    return 0;
}

也可以写成以下这种形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void tarjan(int u, int fa)
{
    low[u] = dfn[u] = ++dfn_clock;
    int child_cnt = 0;
    for (int i = 0; i < g[u].size(); ++i)
    {
        int v = g[u][i];
        if (!dfn[v])
        {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (u != fa && low[v] >= dfn[u])
                ans[u] = true;
            ++child_cnt;
        }
        else if (v != fa)
        {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (u == fa && child_cnt >= 2)
        ans[u] = true;
}