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