tarjan 学习笔记3 割点【tarjan】

作者: wjyyy 分类: tarjan,学习笔记 发布时间: 2018-06-07 16:17

点击量:11

洛谷的这个模板题可以说是相当坑了 【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;
}

 

1
说点什么

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
Mayflyyh Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
Mayflyyh
游客

王骏峣太强了!!!!!

/* */