今日份題目：

力扣數據中心有 n 臺服務器，分別按從 0 到 n-1 的方式進行了編號。它們之間以 服務器到服務器 的形式相互連接組成了一個內部集群，連接是無向的。用 connections 表示集群網絡，connections[i] = [a, b] 表示服務器 a 和 b 之間形成連接。任何服務器都可以直接或者間接地通過網絡到達任何其他服務器。

關鍵連接 是在該集群中的重要連接，假如我們將它移除，便會導致某些服務器無法訪問其他服務器。

請你以任意順序返回該集群內的所有 關鍵連接 。

示例1

輸入：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->vvoid 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;}
};

提交結果

歡迎大家在評論區討論，如有不懂的部分，歡迎在評論區留言！

更新不易，寶子們點個贊支持下，謝謝！