每天一道leetcode：1192. 查找集群内的关键连接（图论&困难&tarjan算法）-Toy模板网

这篇具有很好参考价值的文章主要介绍了每天一道leetcode：1192. 查找集群内的关键连接（图论&困难&tarjan算法）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

今日份题目：

力扣数据中心有 n 台服务器，分别按从 0 到 n-1 的方式进行了编号。它们之间以 服务器到服务器 的形式相互连接组成了一个内部集群，连接是无向的。用 connections 表示集群网络，connections[i] = [a, b] 表示服务器 a 和 b 之间形成连接。任何服务器都可以直接或者间接地通过网络到达任何其他服务器。

关键连接 是在该集群中的重要连接，假如我们将它移除，便会导致某些服务器无法访问其他服务器。

请你以任意顺序返回该集群内的所有 关键连接 。

示例1

每天一道leetcode：1192. 查找集群内的关键连接（图论&困难&tarjan算法）,图论,算法,leetcode,图论,c++,数据结构,迭代加深,图搜索算法

输入：n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
输出：[[1,3]]
解释：[[3,1]] 也是正确的。

示例2

输入：n = 2, connections = [[0,1]]
输出：[[0,1]]

提示

2 <= n <= 105
n - 1 <= connections.length <= 105
0 <= ai, bi <= n - 1
ai != bi
不存在重复的连接

题目思路

根据关键连接的定义，我们可以将题目翻译为，找出删除会导致连通图不连通的点，进而翻译为找到删除后会导致图不连通的边的两点，也就是图论中所说的割边。使用tarjan算法找到割边。

tarjan算法是一种由Robert Tarjan提出的求解有向图强连通分量的线性时间的算法。所谓强连通，就是说两个顶点可以相互通达。Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。

该题直接使用递归，没有涉及堆栈。其中有两个关键数组：dfn和low，dfn可以简单理解为记录我这个点是第几个被遍历到的（时间戳），low可以理解为我的父节点的时间戳。注意，是父节点，不是祖父甚至祖祖父。具体过程可以看我的代码注释。

这道题目有些难，我也是第一次接触到tarjan算法，欢迎懂的小伙伴在评论区科普一下，我也是从网上找的过程，但和本题的不太一样，我就直接读的代码，如果不对欢迎评论指出，谢谢！

代码

class Solution 
{
public:
    unordered_map<int,unordered_set<int>> connect;    
    vector<vector<int>> ans;
//------------------------ tarjan算法找割边 ------------------------//
    int dfn[200000]={0};      //节点搜索的次序编号，记录节点时间戳
    int low[200000]={0};      //子树能够追溯到的最早的栈中节点的次序号，即可以回溯到的最早的时间点
    int time=1;               //全局时间，时间戳
    //当dfn(u)=low(u)时，以u为根的搜索子树上所有节点是一个强连通分量。
    //dfn的值表示第几个被遍历到
    //low的值表示最早的连接我的点，初始值与dfn一样，后续更新为相连的最小时间戳的那个点的low值
    //全局变量time用来表示遍历到第几个了，用于提供dfn的值
    //默认边的表示是u->v

    void tarjan(int u,int parent)
    {
        //初始dfn和low的值都是时间戳
        dfn[u]=time;
        low[u]=time;
        time++;

        for(int v:connect[u]) //遍历u点的所有邻接点
        {
            if(v==parent) continue; //遍历到已经遍历过的节点了(把我引来的节点)
            if(dfn[v]==0) //由于初始化为0，所以等于0表示该节点还没有遍历过
            {
                tarjan(v,u); //判断邻接点的联通情况
                low[u]=min(low[u],low[v]); //low更新为与我相连的节点的最小时间戳
                //节点与每个相连的另一个节点比就能更新为相连的最小时间戳
                if(low[v]>dfn[u]) ans.push_back({u,v}); //是割边的两点的判断条件
            }
            else if(dfn[v]!=0) low[u]=min(low[u],dfn[v]); //该点遍历过了，只更新low
        }
    };

    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) 
    {                    
        for(auto x:connections) //将无向图转化为双向图便于使用tarjan算法
        {
            int u=x[0];
            int v=x[1];
            connect[u].insert(v);
            connect[v].insert(u);
        }
        tarjan(0,-1); //从0开始tarjan算法
        return ans;
    }
};