当前位置: 开发笔记 > 编程语言 > 正文

tarjan求点双联通分量（割点）

作者：黄雅萱介芳 | 来源：互联网 | 2023-10-12 10:40

之前一直对tarjan算法的这几种不同应用比较混淆我太弱啦！被BLO暴虐滚过来用tarjan求点双，很多神犇都给出了比较详细的解释和证明，在这里就不讲了（其实是这只蒟蒻根本不会orz）这里放一下

之前一直对tarjan算法的这几种不同应用比较混淆...我太弱啦！

被BLO暴虐滚过来

用tarjan求点双，很多神犇都给出了比较详细的解释和证明，在这里就不讲了（其实是这只蒟蒻根本不会orz）

这里放一下定义

这篇博客主要讲一讲求割点，点双的板子实现以及详细解释

先yy这样一道题：

有n个点，m条边，保证给出的是一个联通图，求割点

（真·最裸割点）

这道题就可以用下面这份代码实现

#pragma GCC optimize("O2")
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 100001
typedef long long ll;
const int inf=0x3fffffff;
const int maxn=2017;
using namespace std;
inline int read()
{
    int f=1,x=0;char ch=getchar();
    while(ch>'9'|ch<'0')
    {
        if(ch=='-')
        f=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0')
    {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return f*x;
}
struct tsdl{
int to,w,next ;
} edge[N*4];
int tot,head[N],dfn[N],low[N],fa[N],son[N],size[N];
bool iscut[N];
void add(int ui,int vi)
{
edge[++tot].next=head[ui];
edge[tot].to=vi;
head[ui]=tot;
}
void tarjan(int x)
{
dfn[x]=low[x]=++tot;
size[x]=1;
for(int i=head[x];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(v==fa[x])continue;
if(!dfn[v])
{
son[x]++;//x的子树++
fa[v]=x;//v的父亲是x
tarjan(v);
size[x]+=size[v];//x所连节点的个数
low[x]=min(low[x],low[v]);
if(dfn[x]<=low[v])
{
iscut[x]=1;//找到割点 
}
}
else low[x]=min(low[x],dfn[v]);
}
if(fa[x]==0&&son[x]<=1)
iscut[x]=0;//根节点，特判处理 
}
int main()
{
memset(head,-1,sizeof(head));
int n=read(),m=read();
for(int i=1;i<=m;i++)
{
int u=read(),v=read();
add(u,v);
add(v,u);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i])tarjan(i); 
}
for(int i=1;i<=n;i++)
if(iscut[i])cout<}

例如我们输入

5 5
1 2
2 3
1 3
3 4
4 5

程序完美の输出了 3,4

是不是很棒啊x

那么我们要统计点双的数量要怎么处理呢？

显然能发现，我们求出一个割点之后，被割点分成的几部分都能分别与这个割点组成一个点双

那么我们只需要统计每个割点被访问次数即可

更改之后的代码：

#pragma GCC optimize("O2")
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 100001
typedef long long ll;
const int inf=0x3fffffff;
const int maxn=2017;
using namespace std;
inline int read()
{
    int f=1,x=0;char ch=getchar();
    while(ch>'9'|ch<'0')
    {
        if(ch=='-')
        f=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0')
    {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return f*x;
}
struct tsdl{
int to,w,next ;
} edge[N*4];
int tot,head[N],dfn[N],low[N],fa[N],son[N],size[N];
bool iscut[N];
void add(int ui,int vi)
{
edge[++tot].next=head[ui];
edge[tot].to=vi;
head[ui]=tot;
}
int ans;
void tarjan(int x)
{
if(iscut[x])ans++;//统计x1
dfn[x]=low[x]=++tot;
size[x]=1;
int tmp=0;
for(int i=head[x];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(edge[i].to==fa[x])continue;
if(!dfn[v])
{
son[x]++;
fa[v]=x;
tarjan(v);
size[x]+=size[v];
low[x]=min(low[x],low[v]);
if(dfn[x]<=low[v])
{
iscut[x]=1;//找到割点 
ans++;//统计x2
}
}
else low[x]=min(low[x],dfn[v]);
}
if(fa[x]==0&&son[x]<=1)
iscut[x]=0;//根节点，特判处理 
}
int main()
{
memset(head,-1,sizeof(head));
int n=read(),m=read();
for(int i=1;i<=m;i++)
{
int u=read(),v=read();
add(u,v);
add(v,u);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i])tarjan(i); 
}
for(int i=1;i<=n;i++)
if(iscut[i])cout<cout<}

输出就是直接

当然对他做一点小小的改动也可以实现求桥..

只需要对于每次记录iscut 改为记录二维数组cutedge[x][v]即可

需要注意的是这里的条件不同于求割点的小于等于这里需要low[v]严格大于dfn[x]

推荐阅读

go
CodeForces 315B: 线段树与区间更新

题目概述：Sereja 拥有一个由 n 个整数组成的数组 a1, a2, ..., an。他计划执行 m 项操作，这些操作包括更新数组中的特定元素、增加数组中所有元素的值，以及查询数组中的特定元素。 ... [详细]

蜡笔小新 2024-11-23 16:14:08
go
HDU6034 Balala Power!（贪心策略）

题目描述：Balala Power! 时间限制：4000/2000 MS (Java/Other) 内存限制：131072/131072 K (Java/Other)。题目背景及问题描述详见正文。 ... [详细]

蜡笔小新 2024-11-23 15:19:43
import
Java连接MySQL数据库的方法及测试示例

本文详细介绍了如何安装MySQL数据库，并通过Java编程语言实现与MySQL数据库的连接，包括环境搭建、数据库创建以及简单的查询操作。 ... [详细]

蜡笔小新 2024-11-23 18:58:43
utf-8
java 编码与基础数据类型

编码unicode解决了语言不通的问题.但是.unicode又有一个新问题.由于unicode是万国码.把所有国家的文字都编进去了.这就导致一个unicode占用的空间会很大.原来 ... [详细]

蜡笔小新 2024-11-23 09:24:18
char
深入解析C语言中的关键字及其分类

本文将全面介绍C语言中的关键字，并按照功能将其分为数据类型关键字、控制结构关键字、存储类别关键字和其他关键字四大类，旨在帮助读者更好地理解和运用这些基本元素。C语言中共有32个关键字。 ... [详细]

蜡笔小新 2024-11-22 09:55:47
import
Hadoop MapReduce 实战案例：手机流量使用统计分析

本文通过一个具体的Hadoop MapReduce案例，详细介绍了如何利用MapReduce框架来统计和分析手机用户的流量使用情况，包括上行和下行流量的计算以及总流量的汇总。 ... [详细]

蜡笔小新 2024-11-23 20:11:23
import
利用Scrapy构建的数据采集与分析可视化系统

本文探讨了如何使用Scrapy框架构建高效的数据采集系统，以及如何通过异步处理技术提升数据存储的效率。同时，文章还介绍了针对不同网站采用的不同采集策略。 ... [详细]

蜡笔小新 2024-11-23 16:56:38
dll
C/C++ 应用程序的安装与卸载解决方案

本文介绍了如何使用Inno Setup来创建C/C++应用程序的安装程序，包括自动检测并安装所需的运行库，确保应用能够顺利安装和卸载。 ... [详细]

蜡笔小新 2024-11-23 13:44:53
utf-8
SSM框架实战：分页功能实现详解

本文详细介绍如何在SSM（Spring + Spring MVC + MyBatis）框架中实现分页功能。包括分页的基本概念、数据准备、前端分页栏的设计与实现、后端分页逻辑的编写以及最终的测试步骤。 ... [详细]

蜡笔小新 2024-11-23 11:40:33
import
Go语言实现文件读取与终端输出

本文介绍如何使用Go语言编写程序，通过命令行参数指定文件路径，读取文件内容并将其输出到控制台。代码示例中包含了错误处理和资源管理的最佳实践。 ... [详细]

蜡笔小新 2024-11-23 10:57:16
char
【MySQL】frm文件解析

官网说明：http:dev.mysql.comdocinternalsenfrm-file-format.htmlfrm是MySQL表结构定义文件，通常frm文件是不会损坏的，但是如果 ... [详细]

蜡笔小新 2024-11-23 10:29:06
go
D17：C#设计模式之十六观察者模式（Observer Pattern）【行为型】

一、引言今天是2017年11月份的最后一天，也就是2017年11月30日，利用今天再写一个模式，争取下个月（也就是12月份& ... [详细]

蜡笔小新 2024-11-22 19:45:55
char
深入解析 C++ 中的 String 和 Vector

本文详细介绍了 C++ 编程语言中 String 和 Vector 的使用方法及特性，旨在帮助开发者更好地理解和应用这两个重要的容器。 ... [详细]

蜡笔小新 2024-11-22 17:01:09
import
ASCII字符计数器

设计一个算法，用于计算给定字符串中出现的不同ASCII字符数量。该任务将重点考察字符串处理、集合操作以及基础的输入输出技术。 ... [详细]

蜡笔小新 2024-11-23 12:42:16
import
Java Socket编程指南：构建多客户端支持的服务端

本文基于Java官方文档进行了适当修改，旨在介绍如何实现一个能够同时处理多个客户端请求的服务端程序。在前文中，我们探讨了单客户端访问的服务端实现，而本篇将深入讲解多客户端环境下的服务端设计与实现。 ... [详细]

蜡笔小新 2024-11-22 23:16:34

黄雅萱介芳

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章