$割点割顶tarjan$

时间：2023-03-10 02:28:12
$割点割顶tarjan$

原题

$割点割顶tarjan$

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

inline LL read () {

    LL res =  ;

    int f () ;

    char ch = getchar ();

    while (!isdigit(ch)) {

        if (ch == '-') f = - ;

        ch = getchar();

    }

    while (isdigit(ch)) res = (res << ) + (res << ) + (ch ^ ),ch = getchar();

    return res * f ;

}

const int N = +;

int a[N] , nxt [N] , head[N] , dfn[N] , low[N] , cnt , k ;

bool cut[N] , bst[N] ;

inline void Add (int x ,int y) {

    a[++k] = y ; nxt[k] = head[x]; head[x] = k ; return ;

}

inline void tarjan (int u,int mr) {

    int rc = ;

    dfn[u] = low[u] = ++ cnt ;

    for ( register int p = head[u] ; p ; p = nxt[p] ) {

        int v = a[p] ;

        if (! dfn [v]) {

            tarjan ( v , mr ) ;

            low[u] = min ( low[u] , low[v] );

            if (low[v] >= dfn[u] and u != mr) cut[u]=true;

            if (u == mr) rc ++ ;

        }

        low[u] = min ( low[u] , dfn[v] ) ;

    }

    if (u == mr and rc >= ) cut[mr] = true;

}

signed main() {

    int n = read() ;

    int m = read() ;

    int ans =  ;

    for ( register int i =  ;i <= m ; i ++) {

        int x = read() ;

        int y = read() ;

        Add (x,y) ; Add (y,x) ;

    }

    for ( register int i =  ;i <= n ; i ++)

    if ( ! dfn[i] ) tarjan ( i , i ) ;

    for ( register int i =  ;i <= n ; i ++)

    if ( cut[i] ) ans ++ ;

    cout << ans << endl ;

    for ( register int i =  ;i <= n ; i ++)

    if ( cut[i] ) cout << i << ' ' ;

    return  ;

}

首先tarjan求割点的重点就是dfn和low数组的理解。

dfn[i]就是时间戳,即在什么时刻搜索到了点i,

low[i]则是i点能回溯到的dfn最小的祖先,

搜索的时候判断一下当对于点x存在儿子节点y,使得dfn[x]<=low[y]则x一定是割点。

因为只要x的子节点不能回溯到x的上面，就是没有返祖边超过x点，那么割掉x就能造成不连通了

好啦,基本算法介绍完,就要讲几个问题了。

首先，为什么此处

low[a]=min(low[a],dfn[p]);

不能写作

low[a]=min(low[a],low[p]);

在我的理解，由于此处是一张无向图，我们有双向建了边，导致节点可以回溯到它的父节点；

而如果从它的父节点或其父节点的另一棵子树上有向上很多的返祖边，

这时把子节点的low值赋为父节点的low，就可能导致其low==其父节点low<其父节点dfn，

从而使本该是割点的点被忽视了，答案就少了，所以就wa了。

另外本题还有几个注意点：

  1. 给的图不一定是连通图，即求每个联通块的割顶

  2. 输出格式别看错了2333

  3. 链式前向星开边要2倍

随机推荐

  1. [ 浙江大学 程序设计专题 ] 四个专题代码 报告 PPT共享

    [原创]转载请注明出处,请勿用于作弊 专题一: 链接: https://pan.baidu.com/s/11xCwvuPHDkTPeOB_yzJWnw 提取码: prup 专题二: 链接: https ...

  2. NOIP2012提高组D1T3 开车旅行

    n<=100000个山,每个山有高度,从一个山到另一个山代价为高度差,有A和B两人一起开车,A每次选前进方向的次近山,B选最近,保证山高度不同且如果代价相同的山低的代价算小,每次旅行先A走,然后 ...

  3. redis运维相关(基本数据库命令)【十四】

    -----------------------------运维相关------------------------- redis持久化,两种方式1.rdb快照方式2.aof日志方式 --------- ...

  4. VIM使用技巧15

    在vim的插入模式下,有时需要插入寄存器中的文本: 1.使用<C-r>{register} 2.使用<C-r><C-p>{register} 3.使用<C-r ...

  5. Google Protocol Buffer 的使用(一)

    一.什么是Google Protocol Buffer下面是官网给的解释:Protocol buffers are a language-neutral, platform-neutral exten ...

  6. Rooks-LightOj1005（规律）

    A rook is a piece used in the game of chess which is played on a board of square grids. A rook can o ...

  7. noip 2011

    铺地毯 题目描述 为了准备一个独特的颁奖典礼,组织者在会场的一片矩形区域(可看做是平面直角坐标系的第一象限)铺上一些矩形地毯.一共有 n 张地毯,编号从 1 到n .现在将这些地毯按照编号从小到大的顺 ...

  8. JDBC操作MySQL出现：This result set must come from a statement that was created with a result set type of ResultSet.CONCUR_UPDATABLE, ...的问题解决

    错误如下: This result set must come from a statement that was created with a result set type of ResultSe ...

  9. HDU 5074 Hatsune Miku 2014 Asia AnShan Regional Contest dp（水

    简单dp #include <stdio.h> #include <cstring> #include <iostream> #include <map&gt ...

  10. Vuzzer自动漏洞挖掘工具简单分析附使用介绍

    Vuzzer 是由计算机科学机构  Vrije Universiteit Amsterdam.Amsterdam Department of Informatics 以及 International ...

相关文章