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

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]

推荐阅读

string
动态规划算法的基本步骤及最长递增子序列问题详解

本文详细介绍了动态规划算法的基本步骤，包括划分阶段、选择状态、决策和状态转移方程，并以最长递增子序列问题为例进行了详细解析。动态规划算法的有效性依赖于问题本身所具有的最优子结构性质和子问题重叠性质。通过将子问题的解保存在一个表中，在以后尽可能多地利用这些子问题的解，从而提高算法的效率。 ... [详细]

蜡笔小新 2023-12-13 15:38:19
string
在类中定义数组时出错 - Error on defining arrays in class

Iamtryingtomakeaclassthatwillreadatextfileofnamesintoanarray,thenreturnthatarra ... [详细]

蜡笔小新 2023-12-14 17:38:12
import
Java容器中的compareto方法排序原理解析

本文从源码解析Java容器中的compareto方法的排序原理，讲解了在使用数组存储数据时的限制以及存储效率的问题。同时提到了Redis的五大数据结构和list、set等知识点，回忆了作者大学时代的Java学习经历。文章以作者做的思维导图作为目录，展示了整个讲解过程。 ... [详细]

蜡笔小新 2023-12-14 13:53:31
uri
Open judge C16H: Magical Balls 快速幂+逆元问题解析

本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法，并给出了问题的解析和解决方法。详细介绍了问题的背景和规则，并给出了相应的算法解析和实现步骤。通过本文的解析，读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]

蜡笔小新 2023-12-14 12:03:27
string
差分约束系统求解House Man跳跃问题的思路与方法

本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度，要求从最低点跳跃到最高点，每次跳跃的距离不超过D，并且不能改变给定的顺序。通过建立差分约束系统，将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法，并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]

蜡笔小新 2023-12-14 11:49:51
hash
java 线程死锁模拟

1，关于死锁的理解死锁，我们可以简单的理解为是两个线程同时使用同一资源，两个线程又得不到相应的资源而造成永无相互等待的情况。 2，模拟死锁背景介绍：我们创建一个朋友 ... [详细]

蜡笔小新 2023-12-13 19:12:25
hash
[大整数乘法] java代码实现

本文介绍了使用java代码实现大整数乘法的过程，同时也涉及到大整数加法和大整数减法的计算方法。通过分治算法来提高计算效率，并对算法的时间复杂度进行了研究。详细代码实现请参考文章链接。 ... [详细]

蜡笔小新 2023-12-13 11:21:32
string
深入理解Kafka服务端请求队列中请求的处理

本文深入分析了Kafka服务端请求队列中请求的处理过程，详细介绍了请求的封装和放入请求队列的过程，以及处理请求的线程池的创建和容量设置。通过场景分析、图示说明和源码分析，帮助读者更好地理解Kafka服务端的工作原理。 ... [详细]

蜡笔小新 2023-12-12 16:14:59
string
hdu 5439（找规律）的数列求和问题

本文讨论了一个数列求和问题，该数列按照一定规律生成。通过观察数列的规律，我们可以得出求解该问题的算法。具体算法为计算前n项i*f[i]的和，其中f[i]表示数列中有i个数字。根据参考的思路，我们可以将算法的时间复杂度控制在O(n)，即计算到5e5即可满足1e9的要求。 ... [详细]

蜡笔小新 2023-12-12 14:05:58
string
李逍遥寻找仙药的迷阵之旅

本文讲述了少年李逍遥为了救治婶婶的病情，前往仙灵岛寻找仙药的故事。他需要穿越一个由M×N个方格组成的迷阵，有些方格内有怪物，有些方格是安全的。李逍遥需要避开有怪物的方格，并经过最少的方格，找到仙药。在寻找的过程中，他还会遇到神秘人物。本文提供了一个迷阵样例及李逍遥找到仙药的路线。 ... [详细]

蜡笔小新 2023-12-12 13:59:33
string
重入锁（ReentrantLock）学习及实现原理

本文介绍了重入锁（ReentrantLock）的学习及实现原理。在学习synchronized的基础上，重入锁提供了更多的灵活性和功能。文章详细介绍了重入锁的特性、使用方法和实现原理，并提供了类图和测试代码供读者参考。重入锁支持重入和公平与非公平两种实现方式，通过对比和分析，读者可以更好地理解和应用重入锁。 ... [详细]

蜡笔小新 2023-12-11 15:16:28
function
使用nodejs爬取b站番剧数据，计算最佳追番推荐

本文介绍了如何使用nodejs爬取b站番剧数据，并通过计算得出最佳追番推荐。通过调用相关接口获取番剧数据和评分数据，以及使用相应的算法进行计算。该方法可以帮助用户找到适合自己的番剧进行观看。 ... [详细]

蜡笔小新 2023-12-14 20:44:52
hash
Redis数据结构之string应用场景解析

本文介绍了Redis的基础数据结构string的应用场景，并以面试的形式进行问答讲解，帮助读者更好地理解和应用Redis。同时，描述了一位面试者的心理状态和面试官的行为。 ... [详细]

蜡笔小新 2023-12-14 14:02:42
import
求解hdu 1003 java题目的动态规划优化方法

本文讨论了如何优化解决hdu 1003 java题目的动态规划方法，通过分析加法规则和最大和的性质，提出了一种优化的思路。具体方法是，当从1加到n为负时，即sum(1,n)sum(n,s)，可以继续加法计算。同时，还考虑了两种特殊情况：都是负数的情况和有0的情况。最后，通过使用Scanner类来获取输入数据。 ... [详细]

蜡笔小新 2023-12-14 13:11:00
string
阿里云物联网 .NET Core 客户端 | CZGL.AliIoTClient：4. 设备上报属性

阿,里,云,物,联网,net,core,客户端,czgl,aliiotclient, ... [详细]

蜡笔小新 2023-12-14 12:40:20

黄雅萱介芳

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

Tags | 热门标签

RankList | 热门文章