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

--

--

--

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Monitoring Services in OpenShift using Prometheus

Sypri: Synchronization made simple(r)

IP and TCP: A Beginners Guide

Kubernetes — A friendly introduction

*Constructor in Java*

Recreating TechCrunch’s Checkmark Scroll Tracker

How to easily configure and integrate Bootstrap, jquery, tailwind, and many more to Rails.

Multipart Upload to Ceph Object Storage with Python and Boto3

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
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi

More from Medium

AgriTech — USGS LIDAR

BACKTRACKING ALGORITHM

Kruskal’s algorithm

Overcome Imbalance in your datasets — PART II