割点

P3388 【模板】割点（割顶）

题目背景

割点

题目描述

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

输入输出格式

输入格式：

第一行输入(n,m)

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

输出格式：

第一行输出割点个数

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

说明

(n,m)均为100000

(tarjan)图不一定联通！！！

割点：在一个无向连通图中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，原图变成多个连通块，就称这个点集为割点集合。

以上是广义一点的定义，对这个题，要求的为求解所有联通子块的割点，且这个割点集合仅有一个元素。

首先我们明确割点的几个性质：(在一个连通图中)

若点(u)是一个割点，则至少存在一对点(v_1,v_2)，使得(v_1,v_2)的任何一个路径通过点(u)。
对于一颗树，若某个点的入度大于1，则这个点为割点。

有了以上两个性质，我们可以借助(tarjan)求强连通分量的思想求解割点了。

首先，我们同样定义(dfn)和(low)数组，分别代表遍历到某点的时间和某点不通过它父亲下能到达的最小时间

现在开始利用性质1，对于图中某父节点(u)（(u)不为遍历开始的点）和其子节点(v)，在刚进入子节点时，父亲的(dfn)是一定大于子节点的，我们遍历子节点不通过(u)能够到达的边，并用最小值更新(low)数组。遍历结束后，若(low[v]>=dfn[u])即点(v)不通过连接它父亲的边是不能到达它父亲上面的点的（即时间戳小于(dfn[u])的点），那么点(u)即满足了性质1，成为了割点。

对于父节点(u)为遍历使点的时候，我们将连通图(G)看做是一颗树（当存在(u)为某环上的点时，等效为断开与(u)相连的某一条边，因为我们此时本来就是在探讨(u)是否为割点，所以断开其实不影响判断），此时，若这个(u)的入（出）度大于1，则(u)为割点。（其实这个模拟一下也是可以想明白的）

最后说一个问题：在某点更新(low)时，若用来更新的点不能进去（即已经进去），一定要写成(low[now]=min(low[now],dfn[v]))，而不是(low[now]=min(low[now],low[v]);)
为什么？考虑这样一种情况，若点(i)恰好可以到达自己的父亲(u)（不通过父亲找到它的那条边），按照性质1，它父亲(u)仍然是割点。但是，如何它父亲(u)先经过某条边把自己的(low)更新小了，岂不是就错了吗，可以看看这个例子模拟理解一下。

按1,2,3,3,4,5顺序遍历即可

code:

#include <cstdio>
int min(int x,int y){return x<y?x:y;}
const int N=100010;
struct Edge
{
    int to,next;
}edge[N<<1];
int head[N],cnt=0,n,m;
void add(int u,int v)
{
    edge[++cnt].next=head[u];edge[cnt].to=v;head[u]=cnt;
}
int time=0,dfn[N],low[N],ans[N];
void tarjan(int now,int fa)
{
    int child=0;
    dfn[now]=low[now]=++time;
    for(int i=head[now];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(!dfn[v])
        {
            tarjan(v,fa);
            if(low[v]>=dfn[now]&&now!=fa)
                ans[now]=1;
            if(now==fa)
                child++;
            low[now]=min(low[now],low[v]);
        }
        low[now]=min(low[now],dfn[v]);
    }
    if(now==fa&&child>1) ans[now]=1;
}
int main()
{
    scanf("%d%d",&n,&m);
    int u,v;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i,i);
    int cntt=0;
    for(int i=1;i<=n;i++)
        if(ans[i]) cntt++;
    printf("%d
",cntt);
    for(int i=1;i<=n;i++)
        if(ans[i]) printf("%d ",i);
    return 0;
}

2018.6.7