Nikhil Garg
Nikhil Garg

Reputation: 11

Why use two arrays of insertion_time and lowest_insert_time in Tarjans algorithm for Bridges in Graph?

I've been working on the LeetCode problem 1192. Critical Connections in a Network. From various sources, I have the following code:

class Solution {
    int timer = 1;
    void dfs(int node, int parent, vector<int> &vis, vector<int> adj[], int tin[], int low[], vector<vector<int>> &bridges) {
        vis[node] = 1;
        tin[node] = low[node] = timer++;
        for (auto it : adj[node]) {
            if (it == parent) continue;
            if (vis[it] == 0) {
                dfs(it, node, vis, adj, tin, low, bridges);
                low[node] = min(low[it], low[node]);
                // node --- it
                if (low[it] > tin[node]) {
                    bridges.push_back({it, node});
                }
            } else {
                low[node] = min(low[node], tin[it]);
            }
        }
    }
public:
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        vector<int> adj[n];
        for (auto it : connections) {
            int u = it[0], v = it[1];
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        vector<int> vis(n, 0);
        int tin[n];
        int low[n];
        vector<vector<int>> bridges;
        dfs(0, -1, vis, adj, tin, low, bridges);
        return bridges;
    }
};

However, I'm struggling to understand why we use two arrays, tin[] and low[]. Since tin[] is used only to check if a bridge is present, can't we use low[] instead?

For example:

if (vis[it] == 0) {
dfs(it, node, vis, adj, tin, low, bridges);
low[node] = min(low[it], low[node]);
// node --- it
if (low[it] > low[node]) {
    bridges.push_back({it, node});
}

}

I don't understand the intuition for tin[]. Can someone provide an example where tin[] is definitely needed and explain why using only low[] would be incorrect? I am not asking about the usage of arrays in C++ but only to clarify the role of tin[] and low[] in Tarjan's algorithm, which should be language-agnostic.

Upvotes: 0

Views: 51

Answers (0)

Related Questions