【蓝桥杯】tarjan算法

一.概述

Tarjan 算法是基于DFS的算法,用于求解图的连通性问题。

Tarjan 算法可以在线性时间内求出:

无向图:

  • 割点与桥
  • 双连通分量

有向图:

  • 强连通分量
  • 必经点与必经边

 1.割点:

若从图中删除节点 x 以及所有与 x 关联的边之后,图将被分成两个或两个以上的不相连的子图,那么称 x 为图的割点

2.割边/桥:

若从图中删除边 e 之后,图将分裂成两个不相连的子图,那么称 e 为图的割边

3.搜索树:

在无向图中,我们以某一个节点 x 出发进行深度优先搜索,每一个节点只访问一次,所有被访问过的节点与边构成一棵树,我们可以称之为“无向连通图的搜索树”。

4.时间戳:​

时间戳是用来标记图中每个节点在进行深度优先搜索被访问的时间顺序。

dfn[x] 来表示。

5.追溯值:

追溯值用来表示从当前节点 x 作为搜索树的根节点出发,能够访问到的所有节点中,时间戳最小的值 —— low[x]。

二.主要思想

主要思想:

通过一次深度优先遍历,即可找出有向图中的强连通分量。

深度优先遍历有两种方式:

  • 先访问当前节点,再递归相邻节点。
  • 先递归相邻节点,再访问当前节点。

数据结构分析:

  • 我们需要给每个节点一个时间戳,这个时间戳代表了该节点被访问的次序。
  • 同时,还需要一个记录该节点通过自身/子孙能够回到的最早的时间节点。

实现步骤:

  • 我们将所有节点的时间戳初始化为0,构建递归树。
  • 循环所有节点,若dfn[i]==0,则递归访问该节点。
  • 每次递归访问节点时,我们需要将该节点压栈,给时间戳和回溯值赋初值,同时遍历该节点的相邻节点,如果相邻节点的dfn为0,则其还没有被访问过,递归访问该节点,访问结束时,更新回溯值;如果相邻节点已经在栈中,那么就直接更新回溯值。另一种情况是,该节点已经被访问过,但是从栈中弹出,那么不做任何处理。
  • 当遍历完该节点的所有邻接点,我们要判断,该节点的时间戳的回溯值是否相等,若相等,则该节点为强连通分量的根节点。开始弹栈,直到将该节点弹出栈。

三.具体应用

1.求无向图的割边/割点

无向图最最重要的点在于,不能够去处理该节点通向父节点的那条边。

这是有向图和无向图最大的区别。

有向图需要去管在栈里的节点,看能否通过栈里面的节点回到更早的时间,但是为什么要用栈,就是因为一个节点只能访问一次;而对于无向图来说,当前正在访问的节点是通过该节点的父节点访问的,而无向图是不能访问子节点通过父节点的,所以不需要栈。

1)割点的判断方法

  • 该点是根节点并且该点有两个及以上的儿子
  • 该点不是根节点并且该点有儿子并且该点儿子的追溯值大于或等于该点被访问的时间

//tarjan求无向图的割点
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;
const int N=100000;

//链式前向星,用来表示边
struct node{
    int to,next;
}edge[N];
int head[N]={-1},cnt=1;//head[i]表示的是以节点i为始点的边,head[i]中的值表示的是第几条边

int time_flag=0,n,m,res=0,root;
int dfn[N]={0},low[N]={0};//dfn时间戳,low追溯值
bool is_articulation[N]={false};//是否是割点

//加边
void add(int u,int v){
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}

void tarjan(int u){
    dfn[u]=low[u]=++time_flag;
    int child=0;
    
    int v=head[u];
    while(v!=-1){
        int a=edge[v].to;
        if(dfn[a]==0){
            child++;
            tarjan(a);
            low[u]=min(low[u],low[a]);
            if((u==root&&child>1)||(u!=root&&low[a]>=dfn[u])){
                if(!is_articulation[u]){
                    is_articulation[u]=true;
                    res++;
                }
            }
        }
        else{
            low[u]=min(low[u],dfn[a]);
        }
        v=edge[v].next;
    }
    
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;//n个顶点,m条边
    
    //构建好无向图,顶点和边的下标都是从1开始
    memset(head,-1,sizeof(head));
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            root=i;
            tarjan(i);
        }
    }
    cout<<res<<'\n';
    for(int i=1;i<=n;i++){
        if(is_articulation[i])
            cout<<i<<' ';
    }
    cout<<'\n';
    return 0;
}

 

2)割边的判断方法

若x->y这条边是割边,那么low[y]>dfn[x] 

2.求强连通分量(有向图)

//tarjan求强连通分量
#include <iostream>
#include <stack>

using namespace std;
const int N=100;

//链式前向星,用来表示边
struct node{
    int to,next;
}edge[N];
int head[N]={-1};//head[i]表示的是以节点i为始点的边,head[i]中的值表示的是第几条边

int time_flag=0,n,m,cnt=0;
int dfn[N]={0},low[N]={0};//dfn时间戳,low追溯值
bool instack[N]={false};
stack<int> s;

//加边
void add(int u,int v){
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=++cnt;
}

void tarjan_dfs(int u){
    dfn[u]=low[u]=++time_flag;//时间戳和追溯值赋初值
    s.push(u);//节点入栈
    instack[u]=true;
    
    int v=head[u];
    while(v!=-1){//找与u邻接的边
        int a=edge[v].to;
        if(!dfn[a]){//a还没有被访问过
            tarjan_dfs(a);//深度优先访问a节点
            low[u]=min(low[a],low[u]);
        }
        else if(instack[a]){//v已经被访问过
            low[u]=min(dfn[a],low[u]);
        }
        v=edge[v].next;
    }
    if(low[u]==dfn[u]){//表明节点u是强连通分量的根
        int x;
        do{
            x=s.top();
            cout<<x<<' ';
            s.pop();
            instack[x]={false};
        }while(x!=u);
        cout<<endl;
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;//n个顶点,m条边
    
    //构建好有向图,顶点和边的下标都是从1开始
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        add(x, y);
    }
    
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            tarjan_dfs(i);
        }
    }
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/490600.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Java项目】jspm九宫格日志网站

目录 背景 技术简介 系统简介 界面预览 背景 互联网的迅猛发展彻底转变了全球各类组织的管理策略。自20世纪90年代起&#xff0c;中国的政府机关和各类企业便开始探索利用互联网技术来处理管理信息。然而&#xff0c;由于当时网络覆盖不广、用户接受度不高、互联网法律法规…

一文说清:AI大模型在制造业中的应用类型

在过去的几年里&#xff0c;全球制造业的竞争格局正在发生重构&#xff0c;数字化和智能化成为推动变革的关键力量。AI 大模型作为一种通用人工智能技术&#xff0c;其革命性特征体现在能够生成代码、构建人机交互新模式&#xff0c;并与产品研发、工艺设计、生产作业、产品运营…

羊大师解析,孩子喝羊奶的好处

羊大师解析&#xff0c;孩子喝羊奶的好处 孩子喝羊奶有诸多好处。羊奶富含多种营养物质&#xff0c;包括蛋白质、脂肪、维生素和矿物质等&#xff0c;对孩子的生长发育和身体健康都有积极的促进作用。羊奶中的蛋白质含量丰富&#xff0c;且易于消化吸收。这些优质蛋白质可以为…

《海王2》观后感

前言 我原本计划电影上映之后&#xff0c;去电影院观看的&#xff0c;但时间过得飞快&#xff0c;一眨眼这都快4月份了&#xff0c;查了一下&#xff0c;电影院早就没有排片了&#xff0c;所以只能在B站看了&#xff0c;这里不得不吐槽一下&#xff0c;原来花了4块钱购买观看还…

Hudi部署

目录 前言 Hudi的介绍 一、Hudi是什么&#xff1f; 二、Hudi的特点功能和优势 三、Hudi的使用场景 Hudi的搭建部署 一、准备 二、搭建 1&#xff09;搭建JAVA环境和Hadoop环境 2&#xff09;部署zookeeper 3&#xff09;部署Spark on yarn 4&#xff09;部署maven环…

vue-quill-editor和vue-ueditor-wrap富文本编辑器应用

目录 一、vue-quill-editor 1.1、界面展示 1.2、代码介绍 1.2.1、安装 1.2.2、配置 1.2.3、代码应用 1.2.4、提取内容 二、vue-ueditor-wrap 2.1、界面展示 2.2、代码介绍 2.2.1、安装 2.2.2、配置 2.2.3、代码应用 一、vue-quill-editor 1.1、界面展示 文本输出…

[BT]BUUCTF刷题第8天(3.26)

第8天 Web [CISCN2019 华北赛区 Day2 Web1]Hack World 题目明确提示flag在flag表里的flag列&#xff0c;这里先尝试1 返回&#xff1a;你好&#xff0c;glzjin想要一个女朋友。 再尝试1&#xff0c;返回bool(false) 到这里就感觉是布尔盲注的题目类型了&#xff08;虽然我没…

RocketMQ学习笔记:消息存储模型,持久化文件,过期文件删除

这是本人学习的总结&#xff0c;主要学习资料如下 马士兵教育rocketMq官方文档 目录 1、消息存储结构1.1、CommitLog详解1.1.1、CommitLog存储的优点 1.2、ConsumeQueue详解1.3、Index详解 2、持久化文件3、过期文件删除机制3.1、判断过期文件3.2、删除的时机 1、消息存储结构…

大模型时代的向量数据库:原理解析和应用案例

大家好&#xff0c;在人工智能领域&#xff0c;数据处理和加工的需求愈发增加。随着人们深入探索AI高级的应用&#xff0c;如图像识别、语音搜索和推荐引擎等&#xff0c;数据的复杂性也在不断地增加。此时传统的数据库存储方式已不能完全满足需求&#xff0c;向量数据库应运而…

《出海和跨境:明道云HAP支撑全球化业务的能力白皮书》正式发布

随着全球化进程的加速&#xff0c;越来越多的企业开始寻求海外市场的拓展机会。然而在出海道路上&#xff0c;企业面临着诸多挑战&#xff0c;比如跨时区的协作困难、文化差异、信息异步、技术障碍等。 明道云HAP作为一款前沿的企业软件产品&#xff0c;致力于赋能企业跨境经营…

Jwt 报错 : Cannot resolve method ‘parseClaimsJws‘ in ‘JwtParserBuilder‘

Java 环境 Java 版本&#xff1a; jkd11 jwt依赖 <dependency><groupId>io.jsonwebtoken</groupId><artifactId>jjwt</artifactId><version>0.12.5</version></dependency>报错如下图所示 解决方法 在pom.xml中把 jjwt 的依…

2024年【安全员-C证】考试及安全员-C证考试题

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 安全员-C证考试根据新安全员-C证考试大纲要求&#xff0c;安全生产模拟考试一点通将安全员-C证模拟考试试题进行汇编&#xff0c;组成一套安全员-C证全真模拟考试试题&#xff0c;学员可通过安全员-C证考试题全真模拟…

【MySQL】数据库--基础

目录 一、概念&#xff1a; 二、连接数据库[Dos命令] 三、SQL 语句分类 一、概念&#xff1a; MySQL 是一种开源的关系数据库管理系统 (RDBMS)数据库-表的本质仍然是文件 二、连接数据库[Dos命令] mysql -h&#xff1a;mysql服务的主机&#xff08;默认连接到本机服务器&…

2024.3.26学习笔记

今日学习韩顺平java0200_韩顺平Java_对象机制练习_哔哩哔哩_bilibili 今日学习p273-p285 包 包的本质实际上就是创建不同的文件夹/目录来保存类文件 包的三大作用 区分相同名字的类 当类很多时&#xff0c;可以很好的管理类 控制访问范围 包的基本语法 package com.xx…

第九届蓝桥杯大赛个人赛省赛(软件类)真题C 语言 A 组-分数

solution1 直观上的分数处理 #include <iostream> using namespace std; int main() {printf("1048575/524288");return 0; }#include<stdio.h> #include<math.h> typedef long long ll; struct fraction{ll up, down; }; ll gcd(ll a, ll b){if…

UE5、CesiumForUnreal实现海量POI撒点显示与聚合功能

1.实现目标 POI是UE+GIS三维场景中经常需要展示的要素,在UE中常用的表示POI方法有两种。一种是Mesh,即空间的方式;另一种是Widget,即屏幕上的方式,本文这里使用的是Widget屏幕展示的形式来表示POI。 本文这里使用的POI点位数量共3.3w+,采用直接网格聚合算法,并进行性能优…

Excel学习笔记(持续更新-20240326)

写在前面 Excel的学习心得分享&#xff0c;佛系更新。2024/03/26 目录 Excel每次都是以只读模式打开 给Excel设置“开机密码” 保护你的excel不让别人篡改 1.1Excel每次都是以只读模式打开 背景&#xff1a;如果有个工具&#xff0c;每天都有很多人使用&#xff0c;如果是…

Spring设计模式-实战篇之单例模式

实现案例&#xff0c;饿汉式 Double-Check机制 synchronized锁 /*** 以饿汉式为例* 使用Double-Check保证线程安全*/ public class Singleton {// 使用volatile保证多线程同一属性的可见性和指令重排序private static volatile Singleton instance;public static Singleton …

算法系列--动态规划--⼦数组、⼦串系列(数组中连续的⼀段)(1)

&#x1f495;"我们好像在池塘的水底&#xff0c;从一个月亮走向另一个月亮。"&#x1f495; 作者&#xff1a;Mylvzi 文章主要内容&#xff1a;算法系列–动态规划–⼦数组、⼦串系列&#xff08;数组中连续的⼀段&#xff09;(1) 大家好,今天为大家带来的是算法系…

插槽和自定义命令

自定义指令 自定义的指令,定义好之后,在标签内使用,当执行new Vue去模板的时候,看到自定义指令,会将下面的函数,等到特定执行Vue实例阶段触发.模板渲染之后.当触发时的传参的参数的第一个是所写的对象的DOM对象,第二个是是包含指令的对象,对象value是指令赋值.当把指令写到标签…