tarjan 学习笔记3 割点【tarjan】

点击量：500

洛谷的这个模板题可以说是相当坑了 【P3388】【模板】割点（割顶）细节处理不到位总是拿不好分。

目录

题目描述

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

输入输出格式

输入格式：

第一行输入n,m

下面m行每行输入x,y表示x到y有一条边

输出格式：

第一行输出割点个数

第二行按照节点编号从小到大输出节点，用空格隔开

输入输出样例

输入样例#1：

6 7

1 2

1 3

1 4

2 5

3 5

4 5

5 6

输出样例#1：

1

5

说明

n,m均为100000

tarjan 图不一定联通！！！

   首先，图不一定连通（不连通不是已经被割了吗），要求的是每一个分图中的割点，所以枚举1到n没有遍历过的为根节点开始找割点。

   （对于这个题，吐槽一下，下到一个数据，结果数据竟然是n=10000，x=10001卡出巨型RE，于是给点加了100，而且还要升序输出orz）

如何找割点

   对于一个分图，我们的割点这样找：任取一个根节点，开始做dfs，和缩点一样，给遍历到的每个点打下时间戳dfn，初始化low=dfn。如果下一个点没有被遍历过（dfn==0），那么将目前节点的儿子个数son++（后边要用到）。对其继续dfs，如果这个点的low被更新了，说明可以回溯到一个分图中的点。如果下一个点被遍历过（dfn>0），low就可以更新为这个点的dfn（不能为low，不然会调到其他割点的状况）。

   那么low存的就是这个分图中所能回溯到的最早的节点的时间戳，因此如果一个点能回溯到的点的时间戳最早也只能是它的父亲，那么它的父亲就是一个割点。此时父亲的dfn[x]<=min(low[son])。小于等于号意味着可以回溯到自己或自己的孩子。

   我们从它的父亲视角再看一遍，如果一个点x的孩子b的low[b]不再是dfn[b]或dfn[x]，说明它可以回溯到更浅的点，x就在环上，如图：

   比如对于3号点，它可以找孩子直到5为止，而low[5]可以回溯到2，递归过程中会将low[4]也改成2，不满足dfn[3]<=low[4]，同时递归到2时会把low[3]也改为2。

对于low和dfn不同含义的说明

   在缩点中，low和dfn只要不相等，所表达的目的就达到了，而在这里，low是一个点可以回溯到的点，而这个点割去后，它的子节点就不一定能回溯到low了，所以只能回溯到dfn值，代表的是此时能回到的最远距离。

关于根节点

   如果图恰好是一棵树（每棵子树互不连通），那么根节点连接了这每一棵树，如果去掉根节点，那么就能分成多个子树，它们不互相连通，就说明这是割点了。但是如果根节点只有一个可用孩子注，则不满足割去根节点会产生多棵子树的性质，这样根节点就不是割点。

注：可用孩子

   对于一个节点来说，它可能连了不止一条边，但是它可能只有一个可用孩子。什么是可用孩子呢？

 

   简单来说，如果一个节点在一个简单环上，那它会连接两个点，但两个点同属一棵树。因为从其中一个出发，可以走到另一个点，当访问到自己时会结束递归，这样节点就相当于只有一个孩子了。在环上割去这个孩子，不会产生多余的子树，它就不是割点。

   因此，特判根节点时，如果它有两棵或以上的可用子树，它就是一个割点了。

其他

   由于代码风格不同，在不同区域判断割点时，有可能会有重复出现的情况，这时我们就需要判重。判重有两种方法，第一在加入时判断是否已经被加入过；第二时排序时将其合并，显然第一种要方便一点。

   除此之外，要求升序的话，还要对答案进行排序。

Code:（P3388标程）

#include<cstdio>
#include<cstring>
#include<algorithm>
int min(int x,int y){return x<y?x:y;}
struct node//存图
{
    int n;
    node *nxt;
    node(int n)
    {
        this->n=n;
        nxt=NULL;
    }
    node()
    {
        nxt=NULL;
    }
};
node head[100100],*tail[100100];
int n,m;
int ans[100100],sum=0;
int dfn[100100],low[100100],cnt=0;
int from[100100];//判断是否为根节点
bool used[100100];
void tarjan(int x)//dfs判断割点
{
    int son=0;
    dfn[x]=++cnt;//初始化
    low[x]=dfn[x];
    node *p=&head[x];
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        if(dfn[p->n])
            low[x]=min(low[x],dfn[p->n]);
        else
        {
            son++;//没有搜过的点才能算新子树
            from[p->n]=x;
            tarjan(p->n);
            low[x]=min(low[x],low[p->n]);//回溯到最早的节点
            if(used[x])//注意一个点可能在多种情况下是割点
                continue;
            if(from[x]!=0&&low[p->n]>=dfn[x])//不为根节点
            {
                ans[++sum]=x;
                used[x]=true;
            }

            if(from[x]==0&&son>1)//为根节点
            {
                used[x]=true;
                ans[++sum]=x;
            }

        }
    }
}
bool app[100100];//洛谷数据的特殊性
int main()
{
    memset(used,0,sizeof(used));
    int u,v;
    memset(app,false,sizeof(app));
    memset(dfn,0,sizeof(dfn));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n+100;i++)
        tail[i]=&head[i];
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        app[u]=true;
        app[v]=true;
        tail[u]->nxt=new node(v);
        tail[u]=tail[u]->nxt;
        tail[v]->nxt=new node(u);
        tail[v]=tail[v]->nxt;
    }
    for(int i=1;i<=n+100;i++)
        if(!dfn[i]&&app[i])
        {
            from[i]=0;
            tarjan(i);
        }
    printf("%d\n",sum);
    std::sort(ans+1,ans+1+sum);//升序输出
    for(int i=1;i<=sum;i++)
        printf("%d ",ans[i]);
    printf("\n");
    return 0;
}