261. Graph Valid Tree

The problem is trying to solve what is a tree. Actually the tree can be define by following two rules:
1. A graph without cycles.
2. A graph whose nodes are all connected.
Here is good video explaining two popular ways to solve the problem, i.e. Union Find and DFS.
https://www.youtube.com/watch?v=n_t0a_8H8VY
So we can use DFS to check if there is any cycle in the graph. And then after the DFS, we check if all the nodes have been visited.

1:  class Solution {  
2:  public:  
3:    bool validTree(int n, vector<pair<int, int>>& edges) {  
4:      vector<vector<int>> neighbors(n);  
5:      for (int i = 0; i < edges.size(); i++) {  
6:        neighbors[edges[i].first].push_back(edges[i].second);  
7:        neighbors[edges[i].second].push_back(edges[i].first);  
8:      }  
9:      vector<bool> visited(n, false);  
10:      if(dfs(neighbors, visited, 0, -1)) return false;  
11:      for (bool v : visited) {  
12:        if (!v) return false;  
13:      }  
14:      return true;  
15:    }  
16:    bool dfs(vector<vector<int>> &neighbors, vector<bool> &visited, int cur, int parent) {  
17:      visited[cur] = true;  
18:      for (int i = 0; i < neighbors[cur].size(); i++) {  
19:        int neighbor = neighbors[cur][i];  
20:        if ((visited[neighbor] && neighbor != parent) || ((!visited[neighbor]) && dfs(neighbors, visited, neighbor, cur)))  
21:          return true;  
22:      }  
23:      return false;  
24:    }  
25:  };  

Then here is the Union Find version. Note, Union Find is much faster than the DFS.

1:  class Solution {  
2:  public:  
3:    bool validTree(int n, vector<pair<int, int>>& edges) {  
4:      vector<int> ufs(n, 0);  
5:      if (edges.size() != n - 1) return false;  
6:      for (int i = 0; i < ufs.size(); i++) ufs[i] = i;  
7:      for (int i = 0; i < edges.size(); i++) {  
8:        int v = edges[i].first;  
9:        int u = edges[i].second;  
10:        while (v != ufs[v]) v = ufs[v]; // find the set that v belongs to  
11:        while (u != ufs[u]) u = ufs[u]; // find the set that u belongs to  
12:        if (v == u) return false;  
13:        ufs[u] = v;  
14:      }  
15:      return true;  
16:    }  
17:  };