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

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
USACO 2014 Jan - Moolympics区间记录优化算法

题目描述：给定n个半开区间[a, b)，要求使用两个互不重叠的记录器，求最多可以记录多少个区间。解决方案采用贪心算法，通过排序和遍历实现最优解。 ... [详细]

蜡笔小新 2024-12-27 18:14:31
go
Weight the Tree（树形dp）

题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅！－－－－－&# ... [详细]

蜡笔小新 2024-12-26 15:55:56
main
深入理解KMP算法中的next数组：北大OJ 2406题解

本文详细探讨了KMP算法中next数组的构建及其应用，重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现，帮助读者更好地理解KMP算法的核心原理。 ... [详细]

蜡笔小新 2024-12-28 11:30:01
main
Codeforces Round #566 (Div. 2) A~F个人题解

Dashboard-CodeforcesRound#566(Div.2)-CodeforcesA.FillingShapes题意：给你一个的表格，你 ... [详细]

蜡笔小新 2024-12-25 18:41:21
main
UNP 第9章：主机名与地址转换

本章探讨了用于在主机名和数值地址之间进行转换的函数，如gethostbyname和gethostbyaddr。此外，还介绍了getservbyname和getservbyport函数，用于在服务器名和端口号之间进行转换。 ... [详细]

蜡笔小新 2024-12-27 11:26:39
main
C++ 中的数组与动态数组初始化

本文探讨了 C++ 中普通数组和标准库类型 vector 的初始化方法。普通数组具有固定长度，而 vector 是一种可扩展的容器，允许动态调整大小。文章详细介绍了不同初始化方式及其应用场景，并提供了代码示例以加深理解。 ... [详细]

蜡笔小新 2024-12-26 15:38:03
main
VxWorks中的双向链表与环形缓冲应用

本文详细探讨了VxWorks操作系统中双向链表和环形缓冲区的实现原理及使用方法，通过具体示例代码加深理解。 ... [详细]

蜡笔小新 2024-12-26 13:26:16
main
Java 类成员初始化顺序与数组创建

本文探讨了Java中类成员的初始化顺序、静态引入、可变参数以及finalize方法的应用。通过具体的代码示例，详细解释了这些概念及其在实际编程中的使用。 ... [详细]

蜡笔小新 2024-12-27 19:39:42
main
C++实现经典排序算法

本文详细介绍了七种经典的排序算法及其性能分析。每种算法的平均、最坏和最好情况的时间复杂度、辅助空间需求以及稳定性都被列出，帮助读者全面了解这些排序方法的特点。 ... [详细]

蜡笔小新 2024-12-27 19:25:14
main
使用 Azure Service Principal 和 Microsoft Graph API 获取 AAD 用户列表

本文介绍了一段通用代码示例，该代码不仅能够操作 Azure Active Directory (AAD)，还可以通过 Azure Service Principal 的授权访问和管理 Azure 订阅资源。Azure 的架构可以分为两个层级：AAD 和 Subscription。 ... [详细]

蜡笔小新 2024-12-27 16:07:12
merge
Java面试题解析

本文详细介绍了Java编程语言中的核心概念和常见面试问题，包括集合类、数据结构、线程处理、Java虚拟机（JVM）、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题，帮助读者更好地理解Java的关键特性和最佳实践。 ... [详细]

蜡笔小新 2024-12-27 13:55:14
audio
Unity 客户端框架设计：UI管理系统的构建

本文详细介绍了如何构建一个高效的UI管理系统，集中处理UI页面的打开、关闭、层级管理和页面跳转等问题。通过UIManager统一管理外部切换逻辑，实现功能逻辑分散化和代码复用，支持多人协作开发。 ... [详细]

蜡笔小新 2024-12-27 10:28:40
go
Objective-C 编程中的关键语法点

本文探讨了 Objective-C 中的一些重要语法特性，包括 goto 语句、块（block）的使用、访问修饰符以及属性管理等。通过实例代码和详细解释，帮助开发者更好地理解和应用这些特性。 ... [详细]

蜡笔小新 2024-12-26 19:42:38
main
Apache Jena 中 Txn.executeWrite 方法详解与代码示例

本文详细介绍了 Apache Jena 库中的 Txn.executeWrite 方法，通过多个实际代码示例展示了其在不同场景下的应用，帮助开发者更好地理解和使用该方法。 ... [详细]

蜡笔小新 2024-12-26 17:55:52
main
Java中访问器与修改器的深入解析

本文详细介绍了Java中的访问器（getter）和修改器（setter），探讨了它们在保护数据完整性、增强代码可维护性方面的重要作用。通过具体示例，展示了如何正确使用这些方法来控制类属性的访问和更新。 ... [详细]

蜡笔小新 2024-12-26 17:25:24

黄雅萱介芳

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

Tags | 热门标签

RankList | 热门文章