Topological sort

Leetcode 207. Course Schedule

class Solution {
public:
bool canFinish(int n, vector<vector<int>>& prerequisites) {
buildGraph(n, prerequisites);
computeIndegrees(n);
for (int i = 0; i < n; ++i) {
int j = 0;
for (; j < n; ++j) {
//at least one has zero indegree
if (!degrees_[j]) break;
}
//no zero indegree nodes. It means we mush have cycles in the graph.
if (j == n) return false;
//if we can go here, it meas degrees_[j] is 0. The following will change it to -1.
--degrees_[j];
for (int &v : graph_[j]) --degrees_[v];
}
return true;
}
private:
vector<vector<int>> graph_;
vector<int> degrees_;
void buildGraph(int n, vector<vector<int>>& prerequisites){
graph_.resize(n);
for (auto &p : prerequisites) graph_[p[1]].push_back(p[0]);
}

void computeIndegrees(int n) {
degrees_.resize(n);
for (auto &adj : graph_)
for (int &v : adj)
++degrees_[v];
}
};
class Solution {
public:
bool canFinish(int n, vector<vector<int>>& prerequisites) {
vector<vector<int>> G(n);
vector<int> degree(n, 0), bfs;
for (auto& e : prerequisites)
G[e[1]].push_back(e[0]), degree[e[0]]++;
for (int i = 0; i < n; ++i) if (!degree[i]) bfs.push_back(i);
for (int i = 0; i < bfs.size(); ++i)
for (int j: G[bfs[i]])
if (--degree[j] == 0) bfs.push_back(j);
return bfs.size() == n;
}

};
class Solution {
public:
bool canFinish(int n, vector<vector<int>>& prerequisites) {
graph_.resize(n);
todo_.resize(n);
done_.resize(n);
buildGraph(n, prerequisites);
for (int i = 0; i < n; i++) {
if (!done_[i] &&!acyclic(i)){
return false;
}
}
return true;
}
private:
vector<vector<int>> graph_;
vector<bool> todo_, done_;
unordered_set<int> this_seen_;

void buildGraph(int n, vector<vector<int>>& prerequisites) {
for (auto &p : prerequisites) graph_[p[1]].push_back(p[0]);
}

bool acyclic(int node) {
if (todo_[node]) {
return false;
}
if (done_[node]) {
return true;
}
todo_[node] = done_[node] = true;
for (int &v : graph_[node]) {
if (!acyclic(v)) {
return false;
}
}
todo_[node] = false;
return true;
}

};
class Solution {
public:
bool canFinish(int n, vector<vector<int>>& prerequisites) {
graph_.resize(n);
todo_.resize(n);
done_.resize(n);
buildGraph(n, prerequisites);
for (int i = 0; i < n; i++) {
//if not explored. Explore it. If a cycle is detected, return false.
if (!done_[i] &&cyclic(i)){
return false;
}
}
return true;
}
private:
vector<vector<int>> graph_;
vector<bool> todo_, done_;
unordered_set<int> this_seen_;

void buildGraph(int n, vector<vector<int>>& prerequisites) {
for (auto &p : prerequisites) graph_[p[1]].push_back(p[0]);
}

bool cyclic(int node) {
//if in this path, we go back to some visited node, then we detect a cycle.
if (todo_[node]) {
return true;
}
//for this path, if we reach to a done node, then the exploration process is ended. And no cycle will be detected as if we do have cycles, the program will be terminated by previous code.
if (done_[node]) {
return false;
}
// set both todo and done as true. Done means we explored this node globally.
// todo is only for this dfs path. This dfs is a local path.
todo_[node] = done_[node] = true;
for (int &v : graph_[node]) {
if (cyclic(v)) {
return true;
}
}
todo_[node] = false;
return false;
}

};
/*
//after dfs, the local path should be set as unvisited as other local path may use this node.
// such as 1
// 0 3
// 2
// If 0->1, 1->3, 0->2 and 2->3, when we explore node 0, we will have two paths
//1) path 013
// the changing process of todo and done will be
// node 0: todo {0:true, 1:false,2:false,3:false },done {0:true, 1:false,2:false,3:false }
// node 1: todo {0:true, 1:true,2:false,3:false },done {0:true, 1:true,2:false,3:false }
// node 3:todo {0:true, 1:true,2:false ,3:true},done {0:true, 1:true,2:false,3:true}
// after visit node3, we touch the bottom of the path, and we will set todo[node] back to false
// we get dfs(3)=false, and
//todo {0:true, 1:true,2:false ,3:false},done {0:true, 1:true,2:false,3:true}
// then we get dfs(1)=false and
//todo {0:true, 1:false,2:false ,3:false},done {0:true, 1:true,2:false,3:true}
// then dfs(0) fasle
////todo {0:false, 1:false,2:false ,3:false},done {0:true, 1:true,2:false,3:true}
//2) path 023.
node 0: todo {0:true, 1:false,2:false ,3:false},done {0:true, 1:true,2:false,3:true}
node 2: todo {0:true, 1:false,2:true ,3:false},done {0:true, 1:true,2:true,3:true}
node 3: as done[3] is true, we can get dfs(3) is true immediate.
todo {0:true, 1:false,2:true ,3:false},done {0:true, 1:true,2:true,3:true}
then dfs(2) is true
todo {0:true, 1:false,2:false ,3:false},done {0:true, 1:true,2:true,3:true}
then dfs(0) is true
todo {0:false, 1:false,2:false ,3:false},done {0:true, 1:true,2:true,3:true}
DONE.
*/

269. Alien Dictionary

class Solution {
public:
string alienOrder(vector<string>& words) {
if (words.size() == 0) return "";
unordered_map<char, int> indegree;
unordered_map<char, unordered_set<char>> graph;

// initialize
for (int i = 0; i < words.size(); i++) {
for (int j = 0; j < words[i].size(); j++) {
char c = words[i][j];
indegree[c] = 0;
}
}

// build graph and record indegree
for (int i = 0; i < words.size() - 1; i++) {
string cur = words[i];
string nex = words[i + 1];
int len = min(cur.size(), nex.size());
for (int j = 0; j < len; j++) {
if (cur[j] != nex[j]) {
unordered_set<char> set = graph[cur[j]];
if (set.find(nex[j]) == set.end()) {
graph[cur[j]].insert(nex[j]); // build graph
indegree[nex[j]]++; // add indegree
}
break;
}
}
}

// topoligical sort
string ans;
queue<char> q;
for (auto& e : indegree) {
if (e.second == 0) {
q.push(e.first);
}
}
while(!q.empty()) {
char cur = q.front();
q.pop();
ans += cur;

if (graph[cur].size() != 0) {
for (auto& e : graph[cur]) {
indegree[e]--;
if (indegree[e] == 0) {
q.push(e);
}
}
}
}

// tell if it is cyclic
return ans.length() == indegree.size() ? ans : "";
}
};
class Solution {
public:
string alienOrder(vector<string>& words) {
if (words.size()==0)return "";
unordered_map<char, int> degree;
unordered_map<char, unordered_set<char>> graph;

// initialize
for (auto & word: words)
for (auto& w : word)
degree[w] = 0;
//build graph
for (int i =0; i<words.size()-1;++i){
string cur = words[i], nxt = words[i+1];
for (int j=0;j<min(cur.size(), nxt.size());++j){
if(cur[j]!=nxt[j]){
char w1 = cur[j], w2 = nxt[j];
auto it = graph[w1].find(w2);
if(it==graph[w1].end()){
graph[w1].insert(w2);
degree[w2]++;
}
break;
}
}
}

//top sort
queue<char> q;
for (auto &v: degree){
if(v.second==0)q.push(v.first);
}
string res;
while(!q.empty()){
char ch = q.front();
res+= ch;
q.pop();
for(auto &j:graph[ch]){
if(--degree[j]==0){
q.push(j);
}
}

}
return res.size()==degree.size()?res:"";
}
};

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store