C++ में ग्राफ वैलिड ट्री - चक्र और कनेक्टिविटी जांच

समस्या विवरण

मान लीजिए हमारे पास n नोड्स हैं जो 0 से n-1 तक लेबल किए गए हैं और अनडायरेक्टेड एज की सूची [u,v] है। हमें एक फ़ंक्शन परिभाषित करना है जो जांचे कि क्या ये एज एक वैध ट्री बनाते हैं या नहीं।

उदाहरण के लिए, यदि n = 5 और edges = [[0,1], [0,2], [0,3], [1,4]] है, तो आउटपुट true होगा।

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

DFS के साथ चक्र पहचान और कनेक्टिविटी जांच:

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

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

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

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

इनपुट

5, {{0,1},{0,2},{0,3},{1,4}}

आउटपुट

1