Apart from the well-known BFS and DFS algorithms, I find the following algorithms useful for Coding Interview.
Topology sort & circle check
- Given directed graph, sort the nodes in graph so that, if exist an edge (u->v), v comes after u in the sorted array.
- We cannot sort if there is at least 1 circle in the graph, (u->v->u), so we need to check whether there is at least 1 circle in the graph.
vector<vector<int>> adj;
vector<bool> visited;
vector<bool> inDfs;
// the sorted order of node
vector<int> q;
int id = n;
bool ok;
void dfs(int u) {
visited[u] = true;
inDfs[u] = true;
for(int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i];
if (!visited[v]) {
dfs(v);
} else if (inDfs[v]) {
ok = false;
return;
}
}
q[id--] = u;
inDfs[u] = false;
}
Runtime: O(n+m)
Practice:
- https://leetcode.com/problems/course-schedule
- https://leetcode.com/problems/course-schedule-ii
- https://leetcode.com/problems/alien-dictionary
- https://leetcode.com/problems/parallel-courses
Dijkstra
Finding the shortest distance between 2 nodes in non-negative weights graph
int dijstra(vector<vector<int>>& edges, int N, int Source) {
vector<ii> a[N+1];
for(auto e: edges) {
int u = e[0], v = e[1], w = e[2];
a[u].push_back(ii(v, w));
}
priority_queue<ii, vector<ii>, greater<ii> > q;
int fx[N+1];
for(int i = 1; i <= N; i++) fx[i] = INT_MAX;
fx[Source] = 0;
q.push(ii(0, Source));
while (q.size()) {
int u = q.top().second;
q.pop();
for(auto pair: a[u]) {
int v = pair.first;
int w = pair.second;
if (fx[v] > fx[u] + w) {
fx[v] = fx[u] + w;
q.push(ii(fx[v], v));
}
}
}
}
Runtime: O(n + m log n)
Practice: https://leetcode.com/problems/network-delay-time
0-1 BFS
Finding the shortest distance between 2 nodes in weights graph, if the weight of each edge is either 0 or 1.
deque<int> q;
q.push_front(s);
vector<int> fx(n, INT_MAX);
fx[s] = 0;
while (!q.empty()) {
int u = q.front();
q.pop_front();
for(auto edge: adj[u]) {
int v = edge.first;
int w = edge.second;
if (fx[v] > fx[u] + w) {
fx[v] = fx[u] + w;
if (w == 0) {
q.push_front(v);
} else {
q.push_back(v);
}
}
}
}
Runtime: O(n + m)
Practice: https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid
Euler circle finding
- An Eulerian cycle exists if and only if the degrees of all vertices are even
- An Eulerian path exists if and only if the number of vertices with odd degrees is two
vector<int> circle;
unordered_set<int> g[100];
void dfs(int u) {
while (!g[u].empty()) {
int v = *g[u].begin();
g[u].erase(v);
g[v].erase(u);
dfs(v);
}
circle.push_back(u);
}
Runtime: O(m)
Practice:
Kruskal - finding Minimum Spaning Tree
int p[10001];
int r[10001];
int find(int i) {
if (i == p[i]) return i;
return (find(p[i]));
}
void merge(int i, int j) {
if (r[i] > r[j]) {
p[j] = i;
} else {
p[i] = j;
if (r[i] == r[j]) r[j]++;
}
}
int kruskal(int n, vector<vector<int>>& connections) {
vector<pair<int, pair<int, int>>> a;
for(auto e: connections) {
int w = e[2];
int u = e[0];
int v = e[1];
a.push_back(make_pair(w, make_pair(u, v)));
}
sort(a.begin(), a.end());
for(int i = 0; i < n; i++) {
p[i] = i;
r[i] = 0;
}
int res = 0;
int count = 0;
for(int i = 0; i < a.size(); i++) {
int u = a[i].second.first;
int v = a[i].second.second;
int uRoot = find(u);
int vRoot = find(v);
if (uRoot != vRoot) {
res += a[i].first;
count++;
merge(uRoot, vRoot);
}
}
return count == n-1 ? res : -1;
}
Runtime: O(m log m)
Practice:
- https://leetcode.com/problems/connecting-cities-with-minimum-cost
- https://leetcode.com/problems/satisfiability-of-equality-equations
- https://leetcode.com/problems/regions-cut-by-slashes
- https://leetcode.com/problems/redundant-connection
- https://leetcode.com/problems/number-of-islands-ii
- https://leetcode.com/problems/optimize-water-distribution-in-a-village
Bipartite Graph Check
Bipartite Graph is a special graph with the following characteristics: The set of vertices V can be partitioned into two disjoint sets V1 and V2 and all edges in (u,v) ∈ E has the property that u ∈ V1 and v ∈ V2.
vector<bool> visit;
vector<bool> color;
bool dfs(int u, bool c) {
visit[u] = true;
color[u] = c;
for(int v: a[u]) {
if (!visit[v]) {
if (!dfs(v, !c)) return false;
} else {
if (color[u] == color[v]) return false;
}
}
return true;
}
Runtime: O(n+m)
Practice: https://leetcode.com/problems/possible-bipartition/
Check if a node is in circle in graph
The idea is to colour node with 3 colors: 0, 1, 2.
If the node is not visited, its color is 0
If the node is in the process of visiting by DFS, its color is 1
If the node dfs process is completed, its color is 2.
int color[10001];
vector<vector<int>> g;
/*
0: white
1: grey
2: black
*/
bool dfs(int u) {
if (color[u] != 0) return color[u] == 2;
color[u] = 1;
for(int v: g[u]) {
if (color[v] != 2) {
if (color[v] == 1 || !dfs(v)) return false;
}
}
color[u] = 2;
return true;
}
Runtime: O(n+m)
Practice: https://leetcode.com/problems/find-eventual-safe-states/
