Showing posts with label directed graph. Show all posts
Showing posts with label directed graph. Show all posts

Wednesday, August 10, 2016

269. Alien Dictionary

I didn't have any clue in first place. So I followed the top rated solution which uses a topology sort algorithm. I made mistakes in
line 12: I was thinking that all the words should follow the same rule pair by pair. So I did two for loops in first place. However, it seems not. This is a typical question that need to be clarified in an interview.
line 13-14: I didn't have these two rows in first place. However, it turns out to be critical otherwise you'll miss those isolated vertices nodes in the graph. For example "wrf" "e". If you don't have these two line, you'll miss "r" and "f" these two nodes.
line 11 & 15: the found variable is really needed. I broke out the second for loop once I found the first different letter in two words. However, that’ll miss the other present letters in the rest of two words.

1:  class Solution {  
2:  public:  
3:    string alienOrder(vector<string>& words) {  
4:      if (words.size() == 0) return "";  
5:      if (words.size() == 1) return words[0];  
6:      // build graph  
7:      unordered_map<char, set<char>> graph;  
8:      for (int i = 0; i+1 < words.size(); i++) {  
9:        string word1 = words[i];  
10:        string word2 = words[i+1];  
11:        bool found = false;  
12:        for (int j = 0; j < max(word1.size(), word2.size()); j++) {  
13:          if (j < word1.size() && graph.find(word1[j]) == graph.end()) graph[word1[j]] = set<char>();  
14:          if (j < word2.size() && graph.find(word2[j]) == graph.end()) graph[word2[j]] = set<char>();  
15:          if (j < word1.size() && j < word2.size() && word1[j] != word2[j] && !found) {  
16:            graph[word1[j]].insert(word2[j]);  
17:            found = true;  
18:          }  
19:        }  
20:      }  
21:      // start topology sort  
22:      vector<bool> visited(26, false);  
23:      vector<bool> path(26, false);  
24:      string res;  
25:      for (auto it = graph.begin(); it != graph.end(); it++) {  
26:        if (!visited[it->first-'a'] && hasCycle(graph, it->first, visited, path, res)) return "";  
27:      }  
28:      reverse(res.begin(), res.end());  
29:      return res;  
30:    }  
31:    bool hasCycle(unordered_map<char, set<char>> &graph, char c, vector<bool> &visited, vector<bool> &path, string &res) {  
32:      if (visited[c-'a']) return false;  
33:      visited[c-'a'] = path[c-'a'] = true;  
34:      for (auto it = graph[c].begin(); it != graph[c].end(); it++) {  
35:        if (path[*it-'a'] || hasCycle(graph, *it, visited, path, res)) return true;  
36:      }  
37:      path[c-'a'] = false;  
38:      res += c;  
39:      return false;  
40:    }  
41:  };  

Sunday, June 26, 2016

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.