मान लीजिए कि हमारे पास n नोड्स हैं और उन्हें 0 से n - 1 तक लेबल किया गया है और अप्रत्यक्ष किनारों की एक सूची भी दी गई है, हमें एक अप्रत्यक्ष ग्राफ में जुड़े घटकों की संख्या खोजने के लिए एक फ़ंक्शन को परिभाषित करना होगा।
इसलिए, यदि इनपुट n =5 और किनारों =[[0, 1], [1, 2], [3, 4]],
जैसा है।
तो आउटपुट 2
. होगाइसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक फ़ंक्शन dfs() को परिभाषित करें, यह नोड, ग्राफ़, विज़िट की गई एक सरणी लेगा,
-
अगर विज़िट किया गया [नोड] गलत है, तो -
-
विज़िट किया गया [नोड] :=सच
-
-
प्रारंभ करने के लिए i:=0, जब i <ग्राफ का आकार [नोड], अद्यतन (i से 1 तक बढ़ाएं), करते हैं −
-
dfs (ग्राफ [नोड, i], ग्राफ़, विज़िट किया गया)
-
-
मुख्य विधि से निम्न कार्य करें -
-
n आकार के देखे गए सरणी को परिभाषित करें
-
यदि नहीं n गैर-शून्य है, तो -
-
एक सरणी ग्राफ़ परिभाषित करें[n]
-
-
इनिशियलाइज़ करने के लिए:=0, जब मैं <किनारों का आकार, अद्यतन (i से 1 बढ़ाएँ), करते हैं -
-
आप:=किनारों[i, 0]
-
वी:=किनारों[i, 1]
-
ग्राफ़ के अंत में v डालें[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