# [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`.

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 in`edges`.

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

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