Tarjan's Algorithm - Explanation and Problems

Tarjan's Algorithm - Explanation and Problem Solving

1. Algorithm Overview

Tarjan's algorithm is used to find Strongly Connected Components (SCCs) in a directed graph. It uses Depth-First Search (DFS) and assigns each node a unique index and a low-link value.

Steps:

  1. Initialize an index counter and an empty stack.
  2. For each node, if it hasn't been visited, perform DFS.
  3. Set the node's index and low-link to the current index.
  4. Push the node onto the stack.
  5. For each neighbor, recursively apply the DFS if it's not visited.
  6. Update the current node's low-link based on the neighbor.
  7. If the node's low-link equals its index, pop stack until the node is found—this is a SCC.

Complexity:

  • Time: O(V + E)
  • Space: O(V) for stack and auxiliary arrays

2. Easy Problems

Problem 1: Count Number of SCCs

void tarjanSCC(int u, int& index, vector& indices, vector& lowlink, stack& stk,
              vector& onStack, vector>& graph, int& sccCount) {
    indices[u] = lowlink[u] = index++;
    stk.push(u);
    onStack[u] = true;

    for (int v : graph[u]) {
        if (indices[v] == -1) {
            tarjanSCC(v, index, indices, lowlink, stk, onStack, graph, sccCount);
            lowlink[u] = min(lowlink[u], lowlink[v]);
        } else if (onStack[v]) {
            lowlink[u] = min(lowlink[u], indices[v]);
        }
    }

    if (lowlink[u] == indices[u]) {
        while (true) {
            int v = stk.top(); stk.pop(); onStack[v] = false;
            if (v == u) break;
        }
        sccCount++;
    }
}

int countSCCs(vector>& graph) {
    int n = graph.size(), index = 0, sccCount = 0;
    vector indices(n, -1), lowlink(n, -1);
    stack stk;
    vector onStack(n, false);

    for (int i = 0; i < n; ++i)
        if (indices[i] == -1)
            tarjanSCC(i, index, indices, lowlink, stk, onStack, graph, sccCount);

    return sccCount;
}

Problem 2: Detect Cycle in Directed Graph

Tarjan's algorithm detects cycles if any SCC contains more than one node.

// Reuse tarjanSCC from above
bool hasCycle(vector>& graph) {
    int n = graph.size(), index = 0;
    vector indices(n, -1), lowlink(n, -1);
    stack stk;
    vector onStack(n, false);
    bool foundCycle = false;

    function dfs = [&](int u) {
        indices[u] = lowlink[u] = index++;
        stk.push(u); onStack[u] = true;

        for (int v : graph[u]) {
            if (indices[v] == -1) {
                dfs(v);
                lowlink[u] = min(lowlink[u], lowlink[v]);
            } else if (onStack[v]) {
                lowlink[u] = min(lowlink[u], indices[v]);
            }
        }

        if (lowlink[u] == indices[u]) {
            int count = 0;
            while (true) {
                int v = stk.top(); stk.pop(); onStack[v] = false;
                count++;
                if (v == u) break;
            }
            if (count > 1) foundCycle = true;
        }
    };

    for (int i = 0; i < n; ++i)
        if (indices[i] == -1)
            dfs(i);

    return foundCycle;
}

3. Intermediate Problems

Problem 3: Find All SCCs

void tarjanAllSCCs(int u, int& index, vector& indices, vector& lowlink, stack& stk,
                  vector& onStack, vector>& graph, vector>& result) {
    indices[u] = lowlink[u] = index++;
    stk.push(u); onStack[u] = true;

    for (int v : graph[u]) {
        if (indices[v] == -1) {
            tarjanAllSCCs(v, index, indices, lowlink, stk, onStack, graph, result);
            lowlink[u] = min(lowlink[u], lowlink[v]);
        } else if (onStack[v]) {
            lowlink[u] = min(lowlink[u], indices[v]);
        }
    }

    if (lowlink[u] == indices[u]) {
        vector scc;
        while (true) {
            int v = stk.top(); stk.pop(); onStack[v] = false;
            scc.push_back(v);
            if (v == u) break;
        }
        result.push_back(scc);
    }
}

Problem 4: Condensed DAG of SCCs

vector> buildSCCDAG(vector>& graph) {
    int n = graph.size(), index = 0;
    vector indices(n, -1), lowlink(n, -1), sccId(n, -1);
    stack stk;
    vector onStack(n, false);
    vector> sccs;

    function dfs = [&](int u) {
        indices[u] = lowlink[u] = index++;
        stk.push(u); onStack[u] = true;

        for (int v : graph[u]) {
            if (indices[v] == -1) {
                dfs(v);
                lowlink[u] = min(lowlink[u], lowlink[v]);
            } else if (onStack[v]) {
                lowlink[u] = min(lowlink[u], indices[v]);
            }
        }

        if (lowlink[u] == indices[u]) {
            vector scc;
            while (true) {
                int v = stk.top(); stk.pop(); onStack[v] = false;
                sccId[v] = sccs.size();
                scc.push_back(v);
                if (v == u) break;
            }
            sccs.push_back(scc);
        }
    };

    for (int i = 0; i < n; ++i)
        if (indices[i] == -1)
            dfs(i);

    vector> dagSet(sccs.size());
    for (int u = 0; u < n; ++u)
        for (int v : graph[u])
            if (sccId[u] != sccId[v])
                dagSet[sccId[u]].insert(sccId[v]);

    vector> dag(sccs.size());
    for (int i = 0; i < dagSet.size(); ++i)
        dag[i] = vector(dagSet[i].begin(), dagSet[i].end());

    return dag;
}

4. Hard Problem

Problem 5: Minimum Path Cover in a DAG (using SCC + matching)

This is an advanced problem involving SCC condensation followed by max bipartite matching.



    #include 
using namespace std;

const int MAXN = 500;

vector graph[MAXN];
vector> sccs;
vector indices(MAXN, -1), lowlink(MAXN, -1), sccId(MAXN, -1);
stack stk;
vector onStack(MAXN);
int idx = 0, sccCount = 0;

// Tarjan's Algorithm
void tarjan(int u) {
    indices[u] = lowlink[u] = idx++;
    stk.push(u);
    onStack[u] = true;

    for (int v : graph[u]) {
        if (indices[v] == -1) {
            tarjan(v);
            lowlink[u] = min(lowlink[u], lowlink[v]);
        } else if (onStack[v]) {
            lowlink[u] = min(lowlink[u], indices[v]);
        }
    }

    if (lowlink[u] == indices[u]) {
        vector scc;
        while (true) {
            int v = stk.top(); stk.pop(); onStack[v] = false;
            sccId[v] = sccCount;
            scc.push_back(v);
            if (v == u) break;
        }
        sccs.push_back(scc);
        sccCount++;
    }
}

// Bipartite graph for SCC DAG
vector sccGraph[MAXN];
bool visited[MAXN];
int matchTo[MAXN];

// DFS-based matching
bool bpm(int u) {
    for (int v : sccGraph[u]) {
        if (visited[v]) continue;
        visited[v] = true;
        if (matchTo[v] == -1 || bpm(matchTo[v])) {
            matchTo[v] = u;
            return true;
        }
    }
    return false;
}

// Main Function
int minimumPathCover(int n) {
    // Step 1: Find SCCs
    for (int i = 0; i < n; ++i)
        if (indices[i] == -1)
            tarjan(i);

    // Step 2: Build condensed DAG
    set> edges;
    for (int u = 0; u < n; ++u)
        for (int v : graph[u])
            if (sccId[u] != sccId[v])
                edges.insert({sccId[u], sccId[v]});

    for (auto [u, v] : edges)
        sccGraph[u].push_back(v);

    // Step 3: Bipartite Matching on DAG
    fill(matchTo, matchTo + sccCount, -1);
    int matching = 0;

    for (int u = 0; u < sccCount; ++u) {
        fill(visited, visited + sccCount, false);
        if (bpm(u)) matching++;
    }

    return sccCount - matching;
}

int main() {
    int n, m;
    cin >> n >> m; // n = nodes, m = edges
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        graph[u].push_back(v);
    }

    cout << "Minimum Path Cover: " << minimumPathCover(n) << endl;
    return 0;
}

Conclusion

Tarjan's algorithm is a powerful tool for graph analysis, especially for identifying strongly connected components and their applications. It is both time and space efficient, and forms the basis for solving many problems in competitive programming and real-world software systems.