Solution Class Reference

Public Member Functions
bool	validTree (int n, vector< vector< int > > &edges)

Detailed Description

Definition at line 5 of file main.cpp.

Member Function Documentation

validTree()

bool Solution::validTree ( int  n, vector< vector< int > > &  edges  )

inline

Definition at line 8 of file main.cpp.

    {
        if ((int)edges.size() != n - 1)
            return false;
 
        // building adjacency list
        unordered_map<int, list<int>> adj;
        for (const auto& edge: edges)
        {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }
 
        stack<pair<int, int>> s; // stack to store (node, parent)
        s.push({0, -1}); // start DFS from node 0 with parent -1
        vector<bool> visited(n, false); // vector to track visited nodes
        int processed = 0;
 
        while (!s.empty())
        {
            auto [node, parent] = s.top();
            s.pop();
 
            if (visited[node])
                return false;
 
            visited[node] = true;
            processed++;
 
            for (int neighbor: adj[node])
            {
                if (!visited[neighbor])
                    s.push({neighbor, node});
                else if (neighbor != parent)
                    return false; // cycle detected
            }
        }
 
        return processed == n; // check if all nodes are visited
    }

Referenced by main().

---

The documentation for this class was generated from the following file:

• main.cpp