141. Linked List Cycle

To find a cycle in the linked list, we can have two pointers, one of which moves one steps once and the other moves two steps once. If the fast pointer reaches NULL, it means there is no cycle, otherwise, the fast pointer will capture the slow pointer again.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    bool hasCycle(ListNode *head) {  
12:      if (head == NULL || head->next == NULL) return false;  
13:      ListNode *slow = head;  
14:      ListNode *fast = head->next;  
15:      while (fast && fast->next) {  
16:        slow = slow->next;  
17:        fast = fast->next->next;  
18:        if (slow == fast) return true;  
19:      }  
20:      return false;  
21:    }  
22:  };  

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

207. Course Schedule

A typical topology sort problem. The following youtube is a very good material explaining topology sort.
https://www.youtube.com/watch?v=XPM9Q2LMxFk&list=PLqD_OdMOd_6YixsHkd9f4sNdof4IhIima&index=11

In this problem, there are three points.
1. use adjacent-list to represent the graph. In c++, the representation can be vector<unordered_set<int>>.
2. To make a successful topology sort, we need to make sure there is no cycle in the graph. This can be done by DFS.
3. We need two vectors to keep track of visited vertex. The visited vector keeps global graph vertex status. The path vector keeps the vertex status in one dfs function, i.e. vertices connected directly or remotely with one particular vertex.

1:  class Solution {  
2:  public:  
3:    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {  
4:      vector<unordered_set<int>> graph(numCourses);  
5:      construct_graph(graph, prerequisites);  
6:      vector<bool> visited(numCourses, false);  
7:      vector<bool> path(numCourses, false);  
8:      for (int i = 0; i < numCourses; i++) {  
9:        if (!visited[i] && dfs(graph, i, path, visited))  
10:          return false;  
11:      }  
12:      return true;  
13:    }  
14:    void construct_graph(vector<unordered_set<int>> &graph, vector<pair<int, int>> &prerequisites) {  
15:      for (int i = 0; i < prerequisites.size(); i++) {  
16:        graph[prerequisites[i].first].insert(prerequisites[i].second);  
17:      }  
18:    }  
19:    bool dfs(vector<unordered_set<int>> &graph, int vertex, vector<bool> &path, vector<bool> &visited) {  
20:      if (visited[vertex]) return false;  
21:      path[vertex] = visited[vertex] = true;  
22:      for (auto v: graph[vertex]) {  
23:        if (path[v] || dfs(graph, v, path, visited)) {  
24:          return true;  
25:        }  
26:      }  
27:      path[vertex] = false;  
28:      return false;  
29:    }  
30:  };   

Note line 21 and line 27, we revert the path[vertex] status to false in the end because path is a reference and we don't find any cycle. The reason we don't have to worry about if dfs() changes the path[v] to false is once we find a cycle we return true all the way up to the top of stack and we don't have to worry about the path again. On the other hand, if no cycle is found, each dfs() will revert the path[vertex] status.