C++-এ Graph Valid Tree: অনির্দেশিত গ্রাফটি বৈধ ট্রি কিনা যাচাই করা

n সংখ্যক নোড (০ থেকে n-1) এবং অনির্দেশিত এজ লিস্ট দেওয়া আছে। এই এজগুলো একটি বৈধ ট্রি (Valid Tree) তৈরি করে কিনা যাচাই করতে হবে। ট্রি হলে: কানেক্টেড থাকতে হবে এবং সাইকেল (cycle) থাকতে পারবে না।

উদাহরণ

ইনপুট: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]

আউটপুট: true

সমাধানের পদ্ধতি (DFS Cycle Detection + Connectivity Check)

1. এজ লিস্ট থেকে অ্যাডজেসেন্সি লিস্ট graph তৈরি করুন।
2. ভিজিটেড অ্যারে visited[n]: ০ = আনভিজিটেড, ১ = ফুলি প্রসেসড, ২ = করেন্ট পাথে (সাইকেল ডিটেকশনের জন্য)।
3. DFS ফাংশন dfs(node, parent, graph, visited):
   • যদি visited[node] == 1 (ইউরুন প্রসেসড), তবে true রিটার্ন।
   • যদি visited[node] == 2 (ব্যাক এজ পাওয়া গেল), তবে সাইকেল আছে → false রিটার্ন।
   • visited[node] = 2 (এন্টারিং)।
   • সব নেইবারের জন্য (প্যারেন্ট ছাড়া) রিকারসিভ dfs কল করুন, ফলাফল AND করে রাখুন।
   • visited[node] = 1 (এক্সিটিং) এবং ফলাফল রিটার্ন করুন।
4. নোড ০ থেকে DFS শুরু করুন। যদি false আসে, তবে false রিটার্ন।
5. সব নোড ভিজিটেড হয়েছে কিনা চেক করুন। অন্য ভিজিটেড ন থাকলে কানেক্টেড নয় → false।
6. সব ঠিক থাকলে 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