C++의 네트워크에서 중요한 연결

n개의 서버가 있다고 가정합니다. 그리고 이들은 0에서 n-1까지 번호가 매겨져 있으며, 연결[i] =[a,b]는 서버 a와 b 간의 연결을 나타내는 네트워크를 형성하는 무방향 서버 간 연결로 연결됩니다. 모든 서버는 직접 연결되거나 다른 서버를 통해 연결됩니다. 이제 중요한 연결은 연결이 제거되면 일부 서버가 다른 서버에 연결할 수 없게 만드는 연결입니다. 우리는 모든 중요한 연결을 찾아야 합니다.

따라서 입력이 n =4이고 연결 =[[0,1],[1,2],[2,0],[1,3]],

그러면 출력은 [[1,3]]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 한 세트 정의

• 어레이 디스크 정의

• 낮은 어레이 정의

• 하나의 2D 배열 ret 정의

• dfs() 함수를 정의하면 노드, par, 하나의 2D 배열 그래프가 필요합니다.

• 노드가 방문 중이면 -

  • 반환

• 방문한 노드에 삽입

• 디스크[노드] :=시간

• 낮은[노드] :=시간

• (시간을 1 증가)

• 그래프[노드]의 모든 요소 x에 대해

  • x가 par와 같으면 -

    • 다음 부분은 무시하고 다음 반복으로 건너뜁니다.

  • x가 방문되지 않은 경우 -

    • dfs(x, 노드, 그래프)

    • low[node] :=low[node]와 low[x]의 최소값

    • 디스크[노드] <낮음[x]이면 -

      • ret

        끝에 { node, x } 삽입

  • 그렇지 않으면

    • low[node] :=low[node] 및 디스크[x]의 최소값

• 기본 방법에서 다음을 수행하십시오 -

  • 디스크의 크기를 n + 1로 설정

  • 낮은 크기를 n + 1로 설정

  • 시간 :=0

  • 크기 그래프 n + 1의 목록 배열 정의

  • initialize i :=0의 경우 i

    • 유 :=v[i, 0]

    • 승 :=v[i, 1]

    • 그래프 끝에 w 삽입[u]

    • 그래프 끝에 u를 삽입[w]

  • dfs(0, -1, 그래프)

  • 리턴 렛

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   set<int> visited;
   vector<int> disc;
   vector<int> low;
   int time;
   vector<vector<int> > ret;
   void dfs(int node, int par, vector<int> graph[]) {
      if (visited.count(node))
      return;
      visited.insert(node);
      disc[node] = low[node] = time;
      time++;
      for (int x : graph[node]) {
         if (x == par)
         continue;
         if (!visited.count(x)) {
            dfs(x, node, graph);
            low[node] = min(low[node], low[x]);
            if (disc[node] < low[x]) {
               ret.push_back({ node, x });
            }
         } else{
            low[node] = min(low[node], disc[x]);
         }
      }
   }
   vector<vector<int> > criticalConnections(int n, vector<vector<int> >& v) {
      disc.resize(n + 1);
      low.resize(n + 1);
      time = 0;
      vector<int> graph[n + 1];
      for (int i = 0; i < v.size(); i++) {
         int u = v[i][0];
         int w = v[i][1];
         graph[u].push_back(w);
         graph[w].push_back(u);
      }
      dfs(0, -1, graph);
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,1},{1,2},{2,0},{1,3}};
   print_vector(ob.criticalConnections(4,v));
}

입력

4, {{0,1},{1,2},{2,0},{1,3}}

출력

[[1, 3, ],]