C++ में अनडायरेक्टेड ग्राफ में कनेक्टेड कंपोनेंट्स की संख्या

समस्या विवरण

मान लीजिए हमारे पास n नोड्स हैं जो 0 से n-1 तक लेबल किए गए हैं और अनडायरेक्टेड एज की एक सूची दी गई है, हमें अनडायरेक्टेड ग्राफ में कनेक्टेड कंपोनेंट्स की संख्या ढूंढने के लिए एक फ़ंक्शन परिभाषित करना है।

उदाहरण के लिए, यदि n = 5 और edges = [[0, 1], [1, 2], [3, 4]] है:

तो आउटपुट 2 होगा।

समाधान दृष्टिकोण

DFS का उपयोग करके कनेक्टेड कंपोनेंट्स गिनें:

1. dfs() फ़ंक्शन परिभाषित करें जो नोड, ग्राफ, विज़िटेड सरणी लेता है:
   • यदि विज़िटेड[नोड] गलत है, तो विज़िटेड[नोड] := true
   • ग्राफ[नोड] के प्रत्येक पड़ोसी के लिए dfs() को पुनरावर्ती रूप से कॉल करें
2. मुख्य विधि से:
   • आकार n की विज़िटेड सरणी परिभाषित करें
   • यदि n शून्य है, तो 0 लौटाएं
   • आकार n की ग्राफ सरणी परिभाषित करें
   • प्रत्येक एज के लिए u, v निकालें और दोनों दिशाओं में ग्राफ में जोड़ें
   • ret := 0
   • i को 0 से n-1 तक लूप करें:
     • यदि विज़िटेड[i] गलत है, तो dfs(i) कॉल करें और ret बढ़ाएं
   • ret लौटाएं

C++ कार्यान्वयन

#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; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<vector<int>> v = {{0,1},{1,2},{3,4}}; 
    cout << (ob.countComponents(5, v)); 
    return 0;
}

इनपुट

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

आउटपुट

2