C++의 무방향 그래프에서 연결된 구성 요소의 수

n개의 노드가 있고 0에서 n - 1까지 레이블이 지정되어 있고 무향 모서리 목록도 제공된다고 가정하면 무향 그래프에서 연결된 구성 요소의 수를 찾기 위해 하나의 함수를 정의해야 합니다.

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

그러면 출력은 2

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

• dfs() 함수를 정의하면 노드, 그래프, 방문이라는 배열이 필요합니다.

• 방문[노드]가 거짓이면 -

  • 방문[노드] :=참

• 초기화 i :=0의 경우, i <그래프[노드]의 크기일 때 업데이트(i를 1만큼 증가), 수행 -

  • dfs(그래프[노드, i], 그래프, 방문)

• 주요 방법에서 다음을 수행하십시오 -

• 크기가 n인 방문 배열 정의

• n이 0이 아닌 경우 -

  • 배열 그래프 정의[n]

• initialize i :=0의 경우, i <모서리의 크기일 때 업데이트(i를 1만큼 증가), 수행 -

  • u :=가장자리[i, 0]

  • v :=가장자리[i, 1]

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

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

• ret :=0

• initialize i :=0의 경우, i

  • 방문하지 않은 경우[i]가 0이 아닌 경우 -

    • dfs(i, 그래프, 방문)

    • (ret 1 증가)

• 리턴 렛

예시

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   void dfs(int node, vector<int< graph[], vector<bool>& visited){
      if(visited[node]) return;
         visited[node] = true;
      for(int i = 0; i < graph[node].size(); i++){
         dfs(graph[node][i], graph, visited);
      }
   }
   int countComponents(int n, vector<vector<int<>& edges) {
      vector <bool> visited(n);
      if(!n) return 0;
         vector <int< graph[n];
      for(int i = 0; i < edges.size(); i++){
         int u = edges[i][0];
         int v = edges[i][1];
         graph[u].push_back(v);
         graph[v].push_back(u);
      }
      int ret = 0;
      for(int i = 0; i < n; i++){
         if(!visited[i]){
            dfs(i, graph, visited);
            ret++;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int<> v = {{0,1},{1,2},{3,4}};
   cout << (ob.countComponents(5, v));
}

입력

5, [[0,1],[1,2],[3,4]]

출력

2