leetcode 查找集群里的关键链接

港控/mmm° 2023-08-17 15:44 76阅读 0赞

链接：[https://leetcode-cn.com/contest/weekly-contest-154/problems/critical-connections-in-a-network/][https_leetcode-cn.com_contest_weekly-contest-154_problems_critical-connections-in-a-network]

> 力扣数据中心有 n 台服务器，分别按从 0 到 n-1 的方式进行了编号。  
> 它们之间以「服务器到服务器」点对点的形式相互连接组成了一个内部集群，其中连接 connections 是无向的。  
> 从形式上讲，connections\[i\] = \[a, b\] 表示服务器 a 和 b 之间形成连接。任何服务器都可以直接或者间接地通过网络到达任何其他服务器。  
> 「关键连接」是在该集群中的重要连接，也就是说，假如我们将它移除，便会导致某些服务器无法访问其他服务器。  
> 请你以任意顺序返回该集群内的所有 「关键连接」。

class Solution {
    public:
        vector<vector<int>> res;//答案
        vector<int> dfn,low;//targan两个重要数组
        vector<vector<int>> g;//存储图
        int num;//编号
        void tarjan(int x,int p)
        {
            dfn[x]=low[x]=++num;
            for(auto y:g[x]){
                if(!dfn[y])//没有编号，也就是没有遍历到过，将它作为x的儿子结点
                {
                    tarjan(y,x);//进行编号搜索
                    low[x]=min(low[y],low[x]);//儿子能到达的最小点，父亲也可以通过儿子到达
                    if(low[y]>dfn[x]){//桥的判断条件(y能达到的最小编号都比x大，说明只有x-y一条边可以联通，就是桥)
                        res.push_back({x,y});
                    }
                }
                else{
                    if(y==p)continue;//重边无意义
                    else{
                        low[x]=min(low[x],dfn[y]);//不在搜索树里面的边可以用来更新low
                    }
                }
            }
        }
        vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
            dfn=low=vector<int>(n+1);
            g=vector<vector<int>>(n+1);
            for(auto t:connections){
                g[t[0]].push_back(t[1]);
                g[t[1]].push_back(t[0]);
            }
            for(int i=0;i<n;++i){
                if(!dfn[i]){
                    tarjan(i,-1);
                }
            }
            return res;
        }
    };

转载于:https://www.cnblogs.com/clear-love/p/11522621.html

[https_leetcode-cn.com_contest_weekly-contest-154_problems_critical-connections-in-a-network]: https://leetcode-cn.com/contest/weekly-contest-154/problems/critical-connections-in-a-network/