จำนวน Connected Components ใน Undirected Graph ใน C++

สมมติว่ามี n โหนดที่ติดป้ายกำกับจาก 0 ถึง n-1 และรายการขอบแบบไม่มีทิศทาง กำหนดฟังก์ชันเพื่อหาจำนวน connected components ใน undirected graph

เช่น ถ้าอินพุทเป็น n = 5 และ edges = [[0, 1], [1, 2], [3, 4]]

ผลลัพธ์จะเป็น 2

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้ −

• กำหนดฟังก์ชัน dfs() รับ node, graph, อาร์เรย์ visited

• ถ้า visited[node] เป็น false แล้ว −

  • visited[node] := true

• ลูป i := 0 ถึงขนาดของ graph[node]-1 ทำ −

  • dfs(graph[node][i], graph, visited)

• จากเมธอดหลักทำดังนี้ −

• กำหนดอาร์เรย์ visited ขนาด n

• ถ้า n ไม่เป็น non-zero แล้ว −

  • กำหนดอาร์เรย์ graph[n]

• ลูป i := 0 ถึงขนาดของ edges-1 ทำ −

  • u := edges[i][0]

  • v := edges[i][1]

  • แทรก v ที่ท้ายของ graph[u]

  • แทรก u ที่ท้ายของ graph[v]

• ret := 0

• ลูป i := 0 ถึง n-1 ทำ −

  • ถ้า visited[i] ไม่เป็น non-zero แล้ว −

    • dfs(i, graph, visited)

    • เพิ่ม ret ขึ้น 1

• คืนค่า ret

ตัวอย่าง

ลองดูการติดตั้งต่อไปนี้เพื่อให้เข้าใจได้ดีขึ้น −

#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