จำนวนส่วนประกอบที่เชื่อมต่อในกราฟที่ไม่มีทิศทางใน C++

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

ดังนั้น หากอินพุตเป็น n =5 และ edge =[[0, 1], [1, 2], [3, 4]],

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

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

• กำหนดฟังก์ชัน dfs() ซึ่งจะรับโหนด กราฟ อาร์เรย์ที่เรียกว่า เยี่ยมชม

• ถ้าเยี่ยมชม[โหนด] จะเป็นเท็จ ดังนั้น −

  • เยี่ยมชม[โหนด] :=จริง

• สำหรับการเริ่มต้น i :=0 เมื่อฉัน <ขนาดของกราฟ[โหนด] อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • dfs(กราฟ[โหนด, i], กราฟ, เข้าชมแล้ว)

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• กำหนดอาร์เรย์ที่เข้าชมขนาด n

• ถ้าไม่ใช่ n จะไม่ใช่ศูนย์ ดังนั้น −

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

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดขอบ อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • u :=edge[i, 0]

  • v :=ขอบ[i, 1]

  • แทรก v ที่ส่วนท้ายของกราฟ[u]

  • ใส่ u ที่ท้ายกราฟ[v]

• ยกเลิก :=0

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • ถ้าไม่ได้เยี่ยมชม[i] จะไม่เท่ากับศูนย์ ดังนั้น −

    • dfs(i, กราฟ, เข้าชมแล้ว)

    • (เพิ่มการถอยกลับโดย 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