强连通分量 -- 割点(割顶)

目录:

简介割点

        割点集合

        割点

实现

         1.暴力

        2.Tarjan


简介割点:

        割点集合:

        在一个无向图中,如果有一个顶点集合,删除这个顶点集合以及这个集合中所有顶点相关联的边以后,图的连通分量增多,就称这个点集为割点集合。

        在无向联通图 G = ( V , E ) 中: 若对于 x ∈ V , 从图中删去节点x以及所有与 x 关联的边之后, G 分裂成两个或两个以上不相连的子图, 则称 x 为 G 的割点。 简而言之, 割点是无向联通图中的一个特殊的点, 删去中这个点后, 此图不再联通, 而所以满足这个条件的点所构成的集合即为割点集合。

        割点:

        如果某个割点集合只含有一个顶点 X(也即 { X } 是一个割点集合),那么 X 称为一个割点。

        设 G 是一个图,x 是 G 的一条边,如果 G - x 的连通分支数大于 G 的连通分支数,则称 x 是 G 的一个桥,或割边。

实现:

        引入一道例题: 洛谷 P3388 【模板】割点(割顶)

        显然割点的板子题,考虑两种做法(本蒟蒻都是先写暴力 QwQ )。

         1.暴力:

        众所周知,暴力及枚举或爆搜,对于割点,写暴力肯定写枚举,每次枚举任意一个点删掉,看是否连通,然而对于这种比较高深的算法,显然枚举会 TLE 。

        2.Tarjan:

        接下来就轮到今天的主角了——Tarjan算法(注意,还有一个求连通分量的算法也叫 Tarjan 算法,与此算法类似)。( Tarjan,全名 Robert Tarjan,美国计算机科学家。)

        首先选定一个根节点,从该根节点开始遍历整个图(使用 DFS )。

        对于根节点,判断是不是割点很简单——计算其子树数量,如果有 2 棵即以上的子树,就是割点。因为如果去掉这个点,这两棵子树就不能互相到达。

        对于非根节点,判断是不是割点就有些麻烦了。我们维护两个数组 dfn[] 和 low[] ,dfn[u] 表示顶点 u 第几个被(首次)访问,low[u] 表示顶点 u 及其子树中的点,通过非父子边(回边),能够回溯到的最早的点( dfn 最小)的 dfn 值(但不能通过连接 u 与其父节点的边)。对于边 (u, to) ,如果 low[to]>=dfn[u] ,此时 u 就是割点。

        但这里也出现一个问题:怎么计算 low[u] 。

        假设当前顶点为u,则默认 low[u]=dfn[u],即最早只能回溯到自身。

        有一条边 (u, to) ,如果 v 未访问过,继续 DFS,DFS 完之后,low[u]=min(low[u], low[to]);

        如果 to 访问过(且 u 不是 to 的父亲),就不需要继续DFS了,一定有 dfn[v]<dfn[u] ,low[u]=min(low[u], dfn[v])。

【代码实现】

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
using namespace std;
struct node//链式前向星存储图
{
    int to;
	int nex;
}mapp[200010];
int n,m,a,b,sum;
int head[100010],tot;
int dfn[100010],cnt;
int low[100010];
bool vis[100010];
void add(int x,int y)//将边(x,y)加入图
{
	mapp[++tot]=(node){y,head[x]};
    head[x]=tot;
    return;
}
void tarjan(int u,int fa)//tarjan求割点
{
    dfn[u]=low[u]=++cnt;//初始
    int son=0;//用于统计子树的数量
    for(int i=head[u];i;i=mapp[i].nex)
    {
        int to=mapp[i].to;
        if (!dfn[to])
        {
            tarjan(to,fa);
            low[u]=min(low[u],low[to]);
            if(low[to]>=dfn[u]&&u!=fa) vis[u]=1;
            if(u==fa) son++;
        }
        low[u]=min(low[u],dfn[to]);
    }
    if(son>=2&&u==fa) vis[u]=1;
    return;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) {scanf("%d%d",&a,&b);add(a,b);add(b,a);}
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,i);
    for(int i=1;i<=n;i++) if(vis[i]) sum++;//统计割点数
    printf("%d\n",sum);
    for(int i=1;i<=n;i++) if(vis[i]) printf ("%d ",i);//输出
    return 0;//完结撒花
}

        又 AC 一道模板题!!! 

强连通分量 -- 割点(割顶)

上一篇:LeetCode 数据结构—搜索二维矩阵 II


下一篇:字符串算法题(2)反转字符串II