C++怎么实现一个Tarjan算法求强连通分量_C++图论高级算法与DFS应用

尼克

发布时间：2025-11-24 21:03:06

429人浏览过

来源于php中文网

原创

Tarjan算法通过DFS遍历和时间戳求有向图的强连通分量，利用dfn和low数组确定SCC根节点，配合栈结构实现O(V+E)时间复杂度的高效求解。

c++怎么实现一个tarjan算法求强连通分量_c++图论高级算法与dfs应用

在有向图中，强连通分量（Strongly Connected Component, SCC）是指图中任意两个顶点都能互相到达的最大子图。Tarjan算法是一种基于深度优先搜索（DFS）的高效算法，能够在O(V + E)的时间复杂度内求出所有强连通分量。

算法核心思想

Tarjan算法利用了DFS的遍历顺序和时间戳来识别强连通分量。每个节点维护两个值：

dfn[u]：节点u被访问的时间戳
low[u]：以u为根的搜索子树中，能通过后向边或横叉边到达的最小时间戳

当递归回溯时，如果发现dfn[u] == low[u]，说明u是一个强连通分量的“根”，此时栈中从u开始的所有节点构成一个SCC。

实现步骤与代码结构

以下是C++实现Tarjan算法的关键步骤：

立即学习“C++免费学习笔记（深入）”；

Noya

让线框图变成高保真设计。

下载

初始化全局时间戳、dfn数组、low数组、标记是否在栈中的数组
对每个未访问的节点启动DFS
在DFS过程中更新dfn和low，并将节点压入栈
回溯时更新父节点的low值
若dfn[u] == low[u]，则弹出栈中元素直到u，这些节点构成一个SCC

#include 
#include 
#include 
using namespace std;

const int MAXN = 1e5 + 5;
vector graph[MAXN];
int dfn[MAXN], low[MAXN], timestamp = 0;
bool inStack[MAXN];
stack st;
vector> sccs;

void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    st.push(u);
    inStack[u] = true;

    for (int v : graph[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (inStack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if (dfn[u] == low[u]) {
        vector scc;
        while (true) {
            int top = st.top();
            st.pop();
            inStack[top] = false;
            scc.push_back(top);
            if (top == u) break;
        }
        sccs.push_back(scc);
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }

    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }

    cout << "Found " << sccs.size() << " SCC(s):\n";
    for (int i = 0; i < sccs.size(); i++) {
        cout << "SCC " << i + 1 << ": ";
        for (int node : sccs[i]) {
            cout << node << " ";
        }
        cout << "\n";
    }

    return 0;
}

使用注意事项与优化建议

Tarjan算法虽然高效，但在实际应用中需要注意以下几点：

图的节点编号通常从1开始，注意数组边界
确保每条边都正确添加到邻接表中
递归深度可能较大，对于大规模图可考虑手动模拟栈避免爆栈
多个测试用例时记得清空全局变量和邻接表

该算法广泛应用于缩点、拓扑排序预处理、2-SAT等问题中，是图论建模的重要工具。

基本上就这些。掌握Tarjan关键在于理解low值的传播机制和栈的作用。多画图模拟几次流程，很容易就能上手。

c++如何开发2d游戏_c++ SFML库图形渲染与碰撞检测【案例】

c++中如何判断二叉树是否是对称的_c++镜像二叉树判断算法

Clang-Tidy如何在c++项目中进行静态代码检查提升代码质量【工程化】

c++如何实现简单的DNS域名解析_c++ getaddrinfo函数与IP地址转换【方法】

C++如何获取命令行参数？（argc, argv详解）

相关标签:

c++ node 工具栈 ai ios stream 全局变量递归栈算法

本站声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

上一篇：C++11有哪些重要的新特性_C++现代编程特性auto、lambda、智能指针概览下一篇：C++怎么使用std::any进行类型安全的动态类型存储_C++类型安全与std::any应用

作者最新文章

Laravel怎么生成二维码图片_Laravel集成Simple-QrCode扩展包与参数设置【实战】

2025-12-31 16:41

c++头文件中的#ifndef/#define/#endif是什么意思防止头文件重复包含【必会技巧】

2025-12-31 16:41

C++如何实现一个简单的哈希表（Hash Table）？（代码示例）

2025-12-31 16:50

Mac如何修复应用程序权限问题_Mac磁盘工具修复权限【教程】

2025-12-31 16:53

浏览器地址栏搜索建议怎么关闭_禁用Chrome的搜索和网址建议【隐私】

2025-12-31 16:54

猎豹浏览器历史记录怎么查看删除猎豹浏览器浏览记录管理【步骤】

2025-12-31 16:55

composer怎么配置多渠道下载源_composer多repositories仓库优先级设置【技巧】

2025-12-31 16:58

Composer的archive命令如何将项目打包？（代码归档技巧）

2025-12-31 17:09

C++如何使用std::bind和占位符？（函数封装）

2025-12-31 17:17

c++怎么使用std::variant多态容器_c++ 17类型安全联合体访问【方法】

2025-12-31 17:33

热门AI工具

DeepSeek

幻方量化公司旗下的开源大模型平台

AI大模型

开放平台

豆包大模型

字节跳动自主研发的一系列大型语言模型

AI大模型

通义千问

阿里巴巴推出的全能AI助手

AI大模型

腾讯元宝

腾讯混元平台推出的AI助手

文档处理

Excel 表格

文心一言

文心一言是百度开发的AI聊天机器人，通过对话可以生成各种形式的内容。

AI大模型

中文写作

讯飞写作

基于讯飞星火大模型的AI写作工具，可以快速生成新闻稿件、品宣文案、工作总结、心得体会等各种文文稿

中文写作

写作工具

即梦AI

一站式AI创作平台，免费AI图片和视频生成。

图片拼接

图画生成

ChatGPT

最最强大的AI聊天机器人程序，ChatGPT不单是聊天机器人，还能进行撰写邮件、视频脚本、文案、翻译、代码等任务。

AI大模型

中文写作

智谱清言 - 免费全能的AI助手

AI大模型

PDF 文档

相关专题

全局变量怎么定义

本专题整合了全局变量相关内容，阅读专题下面的文章了解更多详细内容。

2025.09.18

python 全局变量

本专题整合了python中全局变量定义相关教程，阅读专题下面的文章了解更多详细内容。

2025.09.18

堆和栈的区别

堆和栈的区别：1、内存分配方式不同；2、大小不同；3、数据访问方式不同；4、数据的生命周期。本专题为大家提供堆和栈的区别的相关的文章、下载、课程内容，供大家免费下载体验。

366

2023.07.18

堆和栈区别

堆(Heap)和栈(Stack)是计算机中两种常见的内存分配机制。它们在内存管理的方式、分配方式以及使用场景上有很大的区别。本文将详细介绍堆和栈的特点、区别以及各自的使用场景。php中文网给大家带来了相关的教程以及文章欢迎大家前来学习阅读。

561

2023.08.10

页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章，大家可以免费体验。

388

2023.08.14

php源码安装教程大全

本专题整合了php源码安装教程，阅读专题下面的文章了解更多详细内容。

2025.12.31

php网站源码教程大全

本专题整合了php网站源码相关教程，阅读专题下面的文章了解更多详细内容。

2025.12.31

视频文件格式

本专题整合了视频文件格式相关内容，阅读专题下面的文章了解更多详细内容。

2025.12.31

不受国内限制的浏览器大全

想找真正自由、无限制的上网体验？本合集精选2025年最开放、隐私强、访问无阻的浏览器App，涵盖Tor、Brave、Via、X浏览器、Mullvad等高自由度工具。支持自定义搜索引擎、广告拦截、隐身模式及全球网站无障碍访问，部分更具备防追踪、去谷歌化、双内核切换等高级功能。无论日常浏览、隐私保护还是突破地域限制，总有一款适合你！

2025.12.31

热门下载

网站特效

网站源码

网站素材

前端模板