您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

【洛谷】P3388 【模板】割点(割顶)

题目地址:

https://www.luogu.com.cn/problem/P3388

题目背景:
割点

题目描述:
给出一个 n n n个点, m m m条边的无向图,求图的割点。

输入格式:
第一行输入两个正整数 n , m n,m n,m。下面 m m m行每行输入两个正整数 x , y x,y x,y表示 x x x y y y有一条边。

输出格式:
第一行输出割点个数。第二行按照节点编号从小到大输出节点,用空格隔开。对于全部数据, 1 ≤ n ≤ 2 × 1 0 4 1\leq n \le 2\times 10^4 1n2×104 1 ≤ m ≤ 1 × 1 0 5 1\leq m \le 1 \times 10^5 1m1×105。点的编号均大于 0 0 0小于等于 n n n

可以用Tarjan算法。与求桥类似,可以从任意一个点 u u u开始做DFS,接着开两个数组dfnlowdfn[u]代表第一次访问 u u u时的时间戳,而low[u]代表从 u u u不经由其DFS树的祖宗节点而能走到的时间戳最小的点的时间戳(其祖宗节点可以计入,但是如果经由祖宗节点继续向上能走到时间戳更小的点,这些点就不能计入了。也就是说,这里的low[u]表示从 u u u能“绕上去”的时间戳最小的节点的时间戳)。首先如果 u u u是DFS树根,且其有两个孩子互相不可达(经过 u u u可达不算),那么 u u u显然是割点,因为去掉其之后就会产生至少两个连通块;如果 u u u不是DFS树根,那么要看一下 u u u是否有个孩子 v v v满足low[v] >= dfn[u],如果成立,则说明从 v v v无法不沿着DFS树而绕到 u u u u u u的上方,则说明 u u u是割点。注意这里不能写成low[v] >= low[u],否则有可能 v v v是经过 u u u再向上走到时间戳更小的点的,从而有可能即使 u u u是割点但是漏解了。代码如下:

#include <iostream>
#include <cstring>
using namespace std;

// 边开两倍
const int N = 2e4 + 10, M = 2e5 + 10;
int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
bool cut[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;
    int child = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (!dfn[v]) {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u] && u != from) cut[u] = true;
            // 累加不连通的孩子数
            if (u == from) child++;
        } else 
        	// 这里需要注意,要用dfn[v]来更新low[u],
        	// 防止v能经过DFS树上的某个祖宗走到了时间戳更小的点,从而漏解
        	low[u] = min(low[u], dfn[v]);
    }
	
	// 如果是树根,且有不少于两个孩子,则u也是割点
    if (child >= 2 && u == from) cut[u] = true;
}

int main() {
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while (m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i, i);

    int tot = 0;
    for (int i = 1; i <= n; i++)
        if (cut[i])
            tot++;
    printf("%d\n", tot);

    for (int i = 1; i <= n; i++)
        if (cut[i])
            printf("%d ", i);

    return 0;
}

时间复杂度 O ( n + m ) O(n+m) O(n+m),空间 O ( n ) O(n) O(n)


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进