Reputation: 11
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