मान लीजिए कि हमारे पास n नोड्स हैं जिन्हें 0 से n-1 तक लेबल किया गया है और अप्रत्यक्ष किनारों की एक सूची [u,v] है, हमें यह जांचने के लिए एक फ़ंक्शन परिभाषित करना होगा कि ये किनारे एक वैध पेड़ बनाते हैं या नहीं।
इसलिए, यदि इनपुट n =5, और किनारों =[[0,1], [0,2], [0,3], [1,4]] जैसा है, तो आउटपुट सही होगा
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
फ़ंक्शन dfs() को परिभाषित करें, यह नोड, पैरा, ग्राफ़ और विज़िट नामक एक अन्य सरणी लेगा,
-
अगर विज़िट किया गया [नोड] 1 के समान है, तो -
-
सही लौटें
-
-
यदि विज़िट किया गया [नोड] 2 के समान है, तो -
-
झूठी वापसी
-
-
विज़िट किया गया [नोड] :=2
-
रेट :=सच
-
प्रारंभ करने के लिए i:=0, जब i <ग्राफ का आकार [नोड], अद्यतन (i से 1 तक बढ़ाएं), करते हैं −
-
अगर ग्राफ़ [नोड, i] बराबर नहीं है, तो -
-
ret :=ret और dfs (ग्राफ [नोड, i], नोड, ग्राफ़, विज़िट किया गया)
-
-
-
विज़िट किया गया [नोड] :=1
-
वापसी रिट
-
मुख्य विधि से निम्न कार्य करें -
-
n आकार के देखे गए सरणी को परिभाषित करें और इसे 0 से भरें।
-
सूचियों की एक सूची को परिभाषित करें जिसे n आकार का ग्राफ़ कहा जाता है
-
इनिशियलाइज़ करने के लिए:=0, जब मैं <किनारों का आकार, अद्यतन (i से 1 बढ़ाएँ), करते हैं -
-
यू:=किनारों[i, 0], वी:=किनारों[i, 1]
-
ग्राफ़ के अंत में v डालें[u]
-
ग्राफ़ के अंत में आपको डालें[v]
-
-
अगर dfs(0, -1, ग्राफ़, विज़िट किया गया) गलत है, तो -
-
झूठी वापसी
-
-
इनिशियलाइज़ i :=0 के लिए, जब i
-
अगर विज़िट किया गया [i] शून्य है, तो −
-
झूठी वापसी
-
-
-
सही लौटें
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool dfs(int node, int par, vector <int< graph[], vector <int<& visited){
if (visited[node] == 1)
return true;
if (visited[node] == 2)
return false;
visited[node] = 2;
bool ret = true;
for (int i = 0; i < graph[node].size(); i++) {
if (graph[node][i] != par)
ret &= dfs(graph[node][i], node, graph, visited);
}
visited[node] = 1;
return ret;
}
bool validTree(int n, vector<vector<int<>& edges) {
vector<int< visited(n, 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);
}
if (!dfs(0, -1, graph, visited))
return false;
for (int i = 0; i < n; i++) {
if (!visited[i])
return false;
}
return true;
}
};
main(){
Solution ob;
vector<vector<int<> v = {{0,1},{0,2},{0,3},{1,4}};
cout << (ob.validTree(5,v));
} इनपुट
5, {{0,1},{0,2},{0,3},{1,4}} आउटपुट
1