[Work-In-Progress] Crack Algorithmic Problems with a Systematic Mind-map

visited = [False] * n

def dfs(u) -> None:
    # Avoid revisiting a node. Possible when the graph is cyclic.
    if visited[u]:
        return
    visited[u] = True

    # Do whatever you want with the current node u here.

    # For graph being adjacency list.
    for v in graph[u]:
        dfs(v)
    # For graph being adjacency matrix.
    # for v in range(n):
    #     if (graph[u][v] is not None):  # edge u-v exists.
    #         dfs(v)

# Graph can contain disconnected clusters.
for u in range(n):
    dfs(u)

vector<bool> visited(n, false);

void dfs(int u) {
    // Avoid revisiting a node. Possible even when the graph is acyclic.
    if (visited[u]) return;
    visited[u] = true;

    // Do whatever you want with the current node u here.

    // For graph being adjacency list.
    for (int v : graph[u])
        dfs(v);
    // For graph being adjacency matrix.
    // for (int v = 0; v < n; v++) {
    //     if (graph[u][v] != -1)    // edge u-v exists.
    //         dfs(v);
    // }
}

// Graph can contain disconnected clusters.
for (int u = 0; u < n; u++)
    dfs(u);

# n - total number of nodes
graph = [[] for _ in range(n)]
for u, v in edges:    # edge u->v.
    graph[u].append(v)

# Identify cycle by checking if node is already on the DFS path.
on_path = [False] * n
# Avoid repeated traversal from a visited node.
visited = [False] * n   

has_cycle = False

# Logic for identifying a cycle, given a start node u.
def dfs(u: int) -> None:
    if on_path[u]:
        has_cycle = True
        # return

    # This if-condition of visited should be placed after 
    # if-condition of on_path, so that has_cycle can be set as True.
    if visited[u] or has_cycle:
        return
    visited[u] = True
        
    # Add current node onto the path before entering the next DFS level.
    on_path[u] = True
    for v in graph[u]:
        dfs(v)
    # Remove current node from path before returning to previous DFS level.
    on_path[u] = False

# Deal with disconnected sub-graphs.
for u in range(n):
    dfs(u)
print(f"Does the graph contain any cycle? {has_cycle}")

# n - total number of nodes
vector<vector<int>> graph(n);

for (auto& edge : edges) {    // edge u->v.
    int from = edge[0];
    int to = edge[1];
    graph[from].emplace_back(to);
}

# Identify cycle by checking if node is already on the DFS path.
vector<bool> onPath(n, false);
# Avoid repeated traversal from a visited node.
vector<bool> visited(n ,false);

bool hasCycle = false;

// Logic for identifying a cycle, given a start node u.
void DFS(int u) {
    if (onPath[u]) {
        hasCycle = true;
    }

    // This if-condition of visited should be placed after 
    // if-condition of on_path, so that has_cycle can be set as True.
    if (visited[u] || hasCycle) {
        return;
    }
    visited[u] = true;

    // Add current node onto the path before entering the next DFS level.
    onPath[u] = true;
    for (int v : graph[u]) {
        DFS(v);
    }
    // Remove current node from path before returning to previous DFS level.
    onPath[u] = false;
}

// Deal with disconnected sub-graphs.

for (int u = 0; u < n; u++) 
    DFS(u);

printf("Does the graph contain any cycle? %s", has_cycle ? "Yes" : "No");

visited = [False] * n

def bfs(root) -> None:
    queue = deque([root])    # same as queue = deque(); queue.append（root）
    visited[root] = True

    while queue:
        u = queue.popleft()

        # For graph being adjacency list.
        for v in graph[u]:
            if not visited[v]:
                visited[v] = True
                # Do whatever you want with node u here.

                queue.append(v)

        # For graph being adjacency matrix.
        # for v in range(n):
        #     if (graph[u][v] is not None) \    # edge u-v exists.
        #         and (not visited[v]):       # node v has not been visited.
        #         visited[v] = True
        #         queue.append(v)

# Graph can contain disconnected clusters.
for u in range(n):
    bfs(u)

vector<bool> visited(n, false);

void bfs(int root) {
    queue<int> q({root});
    visited[root] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        // For graph being adjacency list.
        for (int v : graph[u]) {
            if (!visited[v]) {
                visited[v] = true;
                // Do whatever you want with node u here.
                
                q.emplace(v);
            }
        }
        // For graph being adjacency matrix.
        // for (int v = 0; v < n; v++) {
        //     if (graph[u][v] != -1  // edge u-v exists.
        //          && !visited[v]) {  // node v has not been visited.
        //         visited[v] = true;
        //         q.emplace(v);
        //    }
        // }
    }
}

// Graph can contain disconnected clusters.
for (int u = 0; u < n; u++) {
    bfs(u);
}

ids = [None] * n

vector<int> ids(n, -1);

# adjacency matrix n x n. graph[u][v] == 1 if nodes u and v are connected.
graph

idx = 0    # Current cluster id, starts at 0.

# Start BFS from each node 'root', so that we don't miss out any cluster.
for root in range(n):
    if ids[root] is not None:    # visited.
        continue
    
    ids[root] = idx

    q = deque([root])
    while q:
        u = q.popleft()
        # Add all unvisited, adjacent nodes of u into the queue.
        for v in range(n):
            if graph[u][v] == 1 and ids[v] != idx:
                # ('ids[v] != idx' is the same as 'ids[v] is None' here.)
                ids[v] = idx
                q.append(v)

    idx += 1

// adjacency matrix n x n. graph[u][v] == 1 if nodes u and v are connected.
vector<vector<int>> graph = ...;

int idx = 0;    # Current cluster id, starts at 0.

# Start BFS from each node 'root', so that we don't miss out any cluster.
for (int root = 0; root < n; root++) {
    if (ids[root] != -1)    // visited.
        continue;
    
    ids[root] = idx;

    queue<int> q({root});
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        // Add all unvisited, adjacent nodes of u into the queue.
        for (int v = 0; v < n; v++) {
            if (graph[u][v] == 1 && ids[v] != idx) {
            // ('ids[v] != idx' is the same as 'ids[v] is None' here.)
                ids[v] = idx;
                q.emplace(v);
            }
        }
    }
    idx += 1;
}

class UF:
    def __init__(self, n: int):
        # Initialize unique cluster id to every node.
        self.parent = [i for i in range(n)]
        # Number of clusters may be less than n.
        self.num_clusters = n
    
    def union(self, p: int, q: int) -> None:
        """
        Given two nodes in the same cluster, get their roots in parent-link, 
        and connect them to merge two trees into one.
        """ 
        root_p = self.find(p)
        root_q = self.find(q)

        if root_p == root_q:
            return
        self.parent[root_q] = root_p
        self.num_clusters -= 1

    def find(self, x: int) -> int:
        """
        Goals:
        1. Return the root of node x.
        2. SET the parent of every node in the chain from x to root AS the root.
        """
        # Base case of recursion - the root is found.
        if self.parent[x] == x:
            return x

        # Recursively find the root of x.
        root = self.find(self.parent[x])
        self.parent[x] = root    # Goal 2.
        return root    # Goal 1.

    def get_num_clusters(self) -> int:
        return self.num_clusters

class UF {
private:
    vector<int> parent;
    int numClusters;

public:
    UF(int n) {
        // Initialize unique cluster id to every node.
        parent = vector<int>(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }

        // Number of clusters may be less than n.
        numClusters = n;
    }
    
    void Union(int p, int q) {
        /*
        Given two nodes in the same cluster, get their roots in parent-link, 
        and connect them to merge two trees into one.
        */
        int root_p = Find(p);
        int root_q = Find(q);

        if (root_p == root_q) {
            return;
        }
        parent[root_q] = root_p;
        numClusters -= 1;
    }

    int Find(int x) {
        /*
        Goals:
        1. Return the root of node x.
        2. SET the parent of every node in the chain from x to root AS the root.
        */
        // Base case of recursion - the root is found.
        if (parent[x] == x)
            return x;

        // Recursively find the root of x.
        int root = Find(parent[x]);
        parent[x] = root;    // Goal 2.
        return root;    // Goal 1.
    }

    int GetNumClusters() {
        return numClusters;
    }
};  // end of class.

graph    # n x n adjacency matrix
n = len(graph)

# Record which node v has been added to MST, so that 
# other edges towards v won't be added to MST.
in_mst = [False] * n
# When in_mst[v] for all v is true, i.e. mst_nodes == n,
# the mst has been found, and algorithm can terminate before pq is empty.
mst_nodes = 0

weight_sum = 0

# Sometimes not only the total weight is sought for by the problem.
# The exact edges can be also sought for.
adj_edges = defaultdict(list)
# adj_edges[u] is a list of MST edges (weight, v) adjacent to u.

# Each element in pq is (weight, u, v) where weight is the priority.
pq = PriorityQueue()
pq.put((0, 0, None))    # (weight_u, u, parent in MST)

while not pq.empty():
    weight_u, u, parent = pq.get()

    # Ensure that no cycle (redundant edge to u) is added to MST.
    if in_mst[u]:
        continue

    # Add current edge and node u to the MST.
    in_mst[u] = True
    weight_sum += weight_u
    if parent is not None:
        adj_edges[parent].append((weight, u))

    # Early termination after all nodes have been added to the MST.
    mst_nodes += 1
    if mst_nodes == n:
        break    

    # BFS: Add to the pq all eligible edges searched from u.
    for v, weight_v in enumerate(self.graph[u]):
        if u == v:
            continue
        if self.in_mst[v]:
            continue
        pq.put((weight_v, v, u))

print(weight_sum)
print(adj_edges)

vector<vector<int>> graph;    # n x n adjacency matrix
int n = graph.size();

// Record which node v has been added to MST, so that 
// other edges towards v won't be added to MST.
vector<int> in_mst(n, false);
// When in_mst[v] for all v is true, i.e. mst_nodes == n,
// the mst has been found, and algorithm can terminate before pq is empty.
int mst_nodes = 0;

int weight_sum = 0;

// Sometimes not only the total weight is sought for by the problem.
// The exact edges can be also sought for.
unorder_map<int, vector<int>> adj_edges;
// adj_edges[u] is a list of MST edges (weight, v) adjacent to u.


struct State {
    int weight;
    int node;
    int parent;  // -1 means no parent node.

    bool operator<(const State& state) const {
        // "greater" comparison gives a min-heap.
        return weight > state.weight;
    }
};

// Each element in pq is (weight, u, v) where weight is the priority.
priority_queue<State> pq;
pq.push(State{0, 0, -1});  // (weight_u, u, parent in MST)

while (!pq.empty()) {
    const State state = pq.top();
    pq.pop();
    int weight_u = state.weight;
    int u = state.node;
    int parent = state.parent;

    // Ensure that no cycle (redundant edge to u) is added to MST.
    if (in_mst[u]) continue;

    // Add current edge and node u to the MST.
    in_mst[u] = true;
    weight_sum += weight_u;
    if (parent != -1)
        adj_edges[parent].push_back({weight, u});

    // Early termination after all nodes have been added to the MST.
    mst_nodes += 1;
    if (mst_nodes == n)
        break;    

    // BFS: Add to the pq all eligible edges searched from u.
    for (int v = 0; v < n; v++) {
        int weight_v = graph[u][v];
        if (u == v)
            continue;
        if (in_mst[v])
            continue;
        pq.push(State{weight_v, v, u});
    }
} // end of while.

// res: weight_sum, adj_edges

class Kruskal:
    def __init__(self, n: int, sorted_edges: List[List[int]]) -> None:
        self.sorted_edges = sorted_edges

        # Initialize UF with number of clusters equal to number of nodes.
        self.uf = UF(n)

        self.weight_sum = 0

        # Sometimes not only the total weight is sought for by the problem.
        # The exact edges can be also sought for.
        self.mst_edges = []    # Each element is an MST edge (weight, u, v).

        self.build_mst()

    def get_mst_weight(self) -> int:
        return self.weight_sum

    def build_mst(self) -> None:
        for weight, u, v in self.sorted_edges:
            # Early termination after all nodes have been added to the MST.
            if self.uf.get_num_clusters() == 1:
                break

            if self.uf.connected(u, v):
                # Nodes u and v are already in MST.
                # Skip this non-optimal edge.
                continue
            
            # Add the current minimum edge to the MST.
            self.weight_sum += weight
            self.mst_edges.append((weight, u, v))
            self.uf.union(u, v)

        assert self.uf.get_num_clusters() == 1

class Kruskal {
private:
    vector<vector<int>> sorted_edges;
    UF uf;
    int weight_sum = 0;

    // Sometimes not only the total weight is sought for by the problem. The exact edges can be also sought for.
    vector<vector<int>> mst_edges;
    // Each element is an MST edge (weight, u, v).

public:
    Kruskal(int n, vector<vector<int>> edges]) :  {
        sorted_edges = edges;

        // Initialize UF with # of clusters equal to # of nodes.
        uf = UF(n); 
        build_mst();
    }

    int get_mst_weight() const {
        return weight_sum;
    }

    void build_mst() {
        for (auto& edge : sorted_edges) {
            int weight = edge[0];
            int u = edge[1];
            int v = edge[2];
            // Early termination after all nodes have been added to the MST.
            if (uf.GetNumClusters() == 1)
                break;

            if (uf.Connected(u, v)) {
                // Nodes u and v are already in MST.
                // Skip this non-optimal edge.
                continue;
            }
            
            // Add the current minimum edge to the MST.
            weight_sum += weight;
            mst_edges.push_back({weight, u, v});
            uf.Union(u, v);
        }
        // assert self.uf.get_num_clusters() == 1
    }
}; // end of class.

# ignore `shortest_paths[0]` because node index starts from 1.
shortest_paths = [float('inf')] * (n + 1)
# Initialize stops with inf because optimization skips stop_v > stops[v].
stops = [float('inf')] * (n + 1)

# Adjacency List where edges[u] is a list of all nodes v pointed to by u.
# w is the weight of edge u->v.
edges = defaultdict(list)
for u, v, w in times:
    edges[u].append((v, w))

# Record candidate nodes.
pq = PriorityQueue()

# Initialize solution at source node src. Travel to src requires 0 distance.
shortest_paths[src] = 0
# State is (distance, node index, stop).
# (initialize stop == -1 so that second vertex will have stop == 0, third vertex will have stop == 1.)
pq.put((0, src, -1))

# BFS until all edges have been traversed.
while not pq.empty():
    distance_u, u, stop_u = pq.get()

    # Can return early if the problem only requires distance to a particular destination.
    # if u == dst:
    #     return distance_u

    # Unconstraint case only: Filter out any ?->u choices if the best ?->u has been found.
    # if distance_u > shortest_paths[u]:
    #     continue

    if stop_u >= max_stop:
        continue

    for v, w in edges[u]:
        # Do not use shortest_paths[u] here.
        distance_v = distance_u + w
        stop_v = stop_u + 1

        # Check whether reaching v from u gives a better result.
        if shortest_paths[v] > distance_v:
            shortest_paths[v] = distance_v
            stops[v] = stop_v

            # Unconstraint case: choose u->v as the new best edge to reach v.
            # pq.put((distance_v, v))
            # Other choices ?->v existing in pq will be filtered out.

        # Careful not to condition on (distance_v == shortest_paths[v] and stop_v == stops[v]), as it will disable state of v from entering the pq.
        if distance_v > shortest_paths[v] and stop_v > stops[v]:
            continue
        # Constraint case: consider every path to v for the next nodes.
        pq.put((distance_v, v, stop_v)) 

struct State {
    int id;
    int dist;
    int stop;

    bool operator<(const State& state) const {
        // "greater" comparison gives a min-heap.
        return dist > state.dist;
    }
};

vector<int> distTo(n, INT_MAX);
distTo[src] = 0;

vector<int> stop(n, INT_MAX);
stop[src] = -1;

priority_queue<State> pq;
pq.push(State{src, 0, -1});

while (!pq.empty()) {
    // WARN: Do not define `state` as reference to pq.top() here, because it will change after pq.pop().
    const State state = pq.top();
    pq.pop();

    int u = state.id;
    int distToU = state.dist;
    int stopU = state.stop;

    // Do not return early here if shortest path to every node is required.
    if (u == dst)
        return distTo[u];    // or distToU.

    if (stopU == k)
        continue;

    int stopV = stopU + 1;
    for (auto& adj : graph[u]) {
        int v = adj.first;
        int w = adj.second;

        int distToV = distToU + w;
        if (distTo[v] > distToV) {
            distTo[v] = distToV;
            stop[v] = stopV;
            // pq.push(State{v, distToV, stopV});
        }

        if (distToV > distTo[v] && stopV >= stop[v])
            continue;

        pq.push(State{v, distToV, stopV});
    }
}

return -1;

dist_to = [float('inf')] * V
dist_to[src] = 0

vector<int> distTo(V, INT_MAX);
distTo[src] = 0

parent = [None] * V

passes = V - 1
for _ in range(passes):
    # In the current pass, update a clone instead of the result from the previous pass, so that dist_to[u] won't be updated.
    # That is, each pass only moves each node to its adjacent nodes.
    clone = dist_to.copy()

    for u, v, dist in edges:    # dist is the weight of edge u->v.
        # Update clone from dist_to[u] and current edge weight.
        dist_to_v = dist_to[u] + dist
        if clone[v] > dist_to_v:
            clone[v] = dist_to_v;
            parent[v] = u

    dist_to = clone

return dist_to

vector<int> parent(V, -1); // Default value -1 is simply a placeholder.

for (int k  = 0; k < V-1; k++) {
    vector<int> clone(distTo.begin(), distTo.end());
    for (auto& time : times) {
        int u = time[0];
        int v = time[1];
        int w = time[2];

        if (distTo[u] != INT_MAX) {
            int distToV = distTo[u] + w;
            if (clone[v] > distToV) {
                clone[v] = distToV;
                parent[v] = u;
            }
        }
    }
    distTo = clone;
}

// Retrieve the path from src to any node x.
vector<int> path{x};
int u = x;
while (u != src) {
    u = parent[u];
    path.emplace_back(u);
}
reverse(path.begin(), path.end());

# 2D array.
rows = 2
columns = 3
dp = [[0] * columns for _ in range(rows)]
"""
dp: [[0,0,0]
     [0,0,0]]
"""

// 2D array.
row = 2
col = 3

vector<vector<int>> dp(row, vector<int>(col, 0));

/*
dp: {{0,0,0},
     {0,0,0}}
*/

#include <list>

list<char> li;
li.emplace_back('a');

li.emplace_back('b');
list<char>::iterator bIt = std::prev(li.end());

li.emplace_back('c');

li.insert(bIt, 'd');  // insert 'd' before 'b'.

li.erase(bIt);  // remove 'b' via its iterator.

for (auto it = li.begin(); it != li.end(); it++) {
    cout << *it << endl;
}
/*
print:
a
d
c
*/

from collections import deque
stack = deque()
stack.append((4, 'a'))
stack.append((5, 'b'))
obj = stack.pop()
# obj: (5, 'b')

# deque has no empty() method, unlike PriorityQueue which has.
while stack:
    stack.pop()

#include <stack>
stack<int> = s({1,2,3});
s.emplace(4);
s.emplace(5);
int val = s.top();
s.pop();    // return void.

while (!s.empty()) {
    ...
}

set1 = set()    # WARN: {} is initialized as a dictionary.
set1.add((4, 'a'))
set1.add((5, 'b'))
set1.add((6, 'c'))
set1.remove((6, 'c'))    # remove a specific item.
obj = set.pop()    # remove a random item.

set<int> s({-1,2});    // or set<int> s = {-1,2};
s.insert(1);
s.insert(-10);

if (s.count(-10) == 1) {
    // value -10 exists in the set.
}

size_t numElementsErased = s1.erase(-10);
// numElementsErased == 0 if -10 doesn't exist in the set originally.

int value = -1;
auto it = s.find(value);
if (it != s.end()) {
    printf("value %d exists in the set.", value);
}

# Adjacency Matrix
# 1. Initialization
graph = [[None] * n for _ in range(n)]
for u, v, w in edges:
    graph[u][v] = w

# 2. Access adjacent nodes of node u.
for v, w in enumerate(graph[u]):
    print(v, w)

# 3. Direct access to edge u->v.
print(graph[u][v])

# 4. Find all adjacent nodes of u, by iterating all nodes in the graph.
for v in range(n):
    if (u != v) and (graph[u][v] is not None):
        print(v)

// Adjacency Matrix
// 1. Initialization
vector<vector<int>> graph(n, vector<int>(n, -1));
for (auto& edge : edges) {    // directed edge u->v with weight w.
    int u = edge[0];
    int v = edge[1];
    int w = edge[2];
    graph[u][v] = w;
}

// 2. Access adjacent nodes of node u.
for (int v = 0; v < graph[u].size(); i++) {
    int w = graph[u][v];
    printf("%d %d", v, w);
}

// 3. Direct access to edge u->v.
printf("%d", graph[u][v]);

// 4. Find all adjacent nodes of u, by iterating all nodes in the graph.
for (int v = 0; v < n; v++) {
    if ((v != u) && graph[u][v] != -1) {
        printf("%d ", v);
    }
}

from queue import PriorityQueue
pq = PriorityQueue()    # min-heap by default.

#include <queue>
#include <functional>

priority_queue<int> maxPQ;    // max-heap by default.
priority_queue<int, vector<int>, greater<int>> minPQ;

# Usage 1 - Use tuple to store priority and data.
pq.put((5, 'a'))    # 5 is the priority and 'a' is the data.
pq.put((1, 'c'))
pq.put((1, 'b'))
# `while pq` will not terminate. `pq.empty()` must be used.
while not pq.empty():
    print(pq.get())    
"""
print:
(1, 'b')
(1, 'c')
(5, 'a')
"""

// Usage 1 - Use tuple to store priority and data.
priority_queue<vector<int>,
               vector<vector<int>>,
               greater<vector<int>>> pq2;
pq2.push({5, 99});
pq2.push({1, 98});
pq2.push({1, 97});
while (!pq2.empty())
{
    vector<int> vec = pq2.top();
    printf("%d, %d\n", vec[0], vec[1]);
    pq2.pop();
}
"""
print:
1, 97
1, 98
5, 99
"""

# Usage 2 - Use a class object to store priority and data.
class State:
    def __init__(self, priority, data):
        self.priority = priority
        self.data = data
    
    def __lt__(self, other):
        return self.priority < other.priority

pq.put(State(5, 'a'))
pq.put(State(1, 'b'))
while not pq.empty():
    state = pq.get()
    print(state.priority, state.data)    # print (1, 'b') then (5, 'a').

// Usage 2 - Use a class object to store priority and data.
struct State {
    int priority;
    string data;

    bool operator<(const State& state) const {
        // "greater" comparison gives a min-heap.
        return priority > state.priority;
    }
};

priority_queue<State> pq;
pq.push(State{5, 'a'});
pq.push(State{1, 'b'});
while (!pq.empty()) {
    const State state = pq.top();
    pq.pop();

    // print (1, 'b') then (5, 'a').
    printf("%d, %s\n", state.priority, state.data.c_str());
}