题解 P3388 【【模板】割点（割顶）】

· · 题解

割点

by pascal 太腐图论了

割点的定义

删除

其实就是删除一个图中的节点,然后所有连边删除,如图:

割点

我们删除一个点,要使原本互通的两个(或以上)的节点不互通。(除非被删除的点本身) 如图:

我们要注意:一个图中的割点可能是有多个解的。

割点的解法

I.枚举

我们可以试图割掉随意一个点,然后进行枚举看看连通性。这种方法非常简单,只不过TLE。如图:

很显然如果数据太大,check就会直接爆掉!就此,我们寻找规律。

II.Tarjan

首先我们来认识DFS树是什么。

我们知道,BFS的原理就是寻这一棵树横着找,而DFS就是竖着找。那么我们把树改成图,会不会更神奇。

下图演示了BFS遍历图和DFS遍历图的特点:

我们DFS遍历后的图改成树(先后次序):

我们引进一些术语。

1.树边:就是连接父子的边,也就是上图黑色的边
2.回边:有些时候图不是完完全全的树,所以多出来的边就是回边,也就是红色的那个。
3.(为了习惯所以叫)祖宗:父亲及以上。

真·Tarjan

以下内容出自nullzx。

显然如果节点U的所有孩子节点可以不通过父节点U而访问到U的祖先节点,
那么说明此时去掉节点U不影响图的连通性,U就不是割点。
相反,如果节点U至少存在一个孩子顶点，必须通过父节点U才能访问到U的祖先节点,
那么去掉节点U后，顶点U的祖先节点和孩子节点就不连通了,说明U是一个割点。

我们定义三个数组:

dnf数组的下标表示顶点的编号，数组中的值表示该顶点在DFS中的遍历顺序(或者说时间戳)，每访问到一个未访问过的顶点，访问顺序的值（时间戳）就增加1。
子顶点的dfn值一定比父顶点的dfn值大（但不一定恰好大1，比如父顶点有两个及两个以上分支的情况）。
在访问一个顶点后，它的dfn的值就确定下来了，不会再改变。
low数组的下标表示顶点的编号，数组中的值表示DFS中该顶点不通过父顶点能访问到的祖先顶点中最小的顺序值（或者说时间戳）。
每个顶点初始的low值和dfn值应该一样，在DFS中，我们根据情况不断更新low的值。
假设由顶点U访问到顶点V。当从顶点V回溯到顶点U时，
如果
dfn[v] < low[u]
那么
low[u] = dfn[v]
如果顶点U还有它分支，每个分支回溯时都进行上述操作，那么顶点low[u]就表示了不通过顶点U的父节点所能访问到的最早祖先节点。
parent数组:下标表示顶点的编号，数组中的值表示该顶点的父顶点编号，
它主要用于更新low值的时候排除父顶点，当然也可以其它的办法实现相同的功能。

案例:

CODE

//140ms-太慢了!

// luogu-judger-enable-o2

Uses math;

var
        reach,next:array[1..200000] of longint;
        cut:array[1..200000] of boolean;
        cnt,dfn,low:array[1..100000] of longint;
        n,m,ans,i,j,x,y,cn,tot:longint;

procedure add(x,y:longint);
begin
        inc(tot);
        reach[tot]:=y;
        next[tot]:=cnt[x];
        cnt[x]:=tot;
end;

procedure tarjan(u,vv:longint);
var
        r,v,i:longint;
begin
        r:=0;
        inc(cn);
        low[u]:=cn;
        dfn[u]:=low[u];
        i:=cnt[u];
        while i<>-1 do
        begin
                v:=reach[i];
                if dfn[v]=0 then
                begin
                        tarjan(v,vv);
                        low[u]:=min(low[u],low[v]);
                        if (low[v]>=dfn[u])and(u<>vv) then
                                cut[u]:=True;
                        if u=vv then
                                inc(r);
                end;
                low[u]:=min(low[u],dfn[v]);
                i:=next[i];
        end;
        if (u=vv)and(r>=2) then
                cut[vv]:=True;
end;

begin
        filldword(cnt,sizeof(cnt) div 4,maxlongint*2+1);
        read(n,m);
        for i:=1 to m do
        begin
                read(x,y);
                add(x,y);
                add(y,x);
        end;

        for i:=1 to n do
                if dfn[i]=0 then
                        tarjan(i,i);

        for i:=1 to n do
                if cut[i] then
                        inc(ans);
        writeln(ans);
        for i:=1 to n do
                if cut[i] then
                        write(i,' ');
end.

好了大家我去腐数论去