[leetcode] Graph Valid Tree


Graph Valid Tree

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Show Hint

    Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together inedges.

    1. Graph contains no circles
    2. E = V – 1.
    3. No isolated node

    DFS

    //What is the definition of a tree?
    //no circles
    //no isolated nodes
    class Solution {
    public:
        bool validTree(int n, vector<pair<int, int>>& edges) {
            if(n != edges.size() + 1) return false;
            if(n <= 3) return true;
            vector<unordered_map<int, int>> graph(n);
            bool isVisited[n];
            memset(isVisited, false, sizeof(isVisited));
            //construct graph
            for(size_t i = 0; i < edges.size(); i++){
                graph[edges[i].first][edges[i].second] = 1;
                graph[edges[i].second][edges[i].first] = 1;
            }
            //DFS search
            return DFS(graph, 0, isVisited);
        }
        bool DFS(vector<unordered_map<int ,int>>& g, int index, bool isVisited[]){
            if(isVisited[index] == true){//visited
                return false;//circle exist
            }
            isVisited[index] = true;//mark as visited
            for(auto it = g[index].begin(); it != g[index].end(); it++){ //BUG HERE, DO NOT ERASE ITERATOR DURING A FOR LOOP!
                int nidx = it->first;
                //remove edges
                if(it->second == 0) continue;
                g[it->first][index] = 0;
                g[index][it->first] = 0;
                if(DFS(g, nidx, isVisited) == false){
                    return false;
                }
            }
            return true;
        }
    };

    Untitled

    Leave a comment

    Your email address will not be published.

    This site uses Akismet to reduce spam. Learn how your comment data is processed.