---
title: "Tarjan's Algorithm in Combinatorics"
description: "Tarjan's Algorithm is a linear-time graph method for finding strongly connected components in Combinatorics, using DFS, low-link values, and a stack."
canonical: "https://fiveable.me/combinatorics/key-terms/tarjans-algorithm"
type: "key-term"
subject: "Combinatorics"
unit: "Unit 11"
---

# Tarjan's Algorithm in Combinatorics

## Definition

Tarjan's Algorithm is a depth-first search method for finding strongly connected components in a directed graph. In Combinatorics, it shows how graph connectivity can be broken into pieces in linear time.

## What It Is

Tarjan's Algorithm is a graph algorithm in Combinatorics that finds strongly connected components in a directed graph. A strongly connected component, or SCC, is a group of vertices where every vertex can reach every other vertex by following the direction of the edges.

The algorithm works by running a Depth-First Search (DFS) and keeping track of two things for each vertex: its discovery index and its low-link value. The discovery index tells you when a vertex was first seen. The low-link value tells you the earliest discovery index reachable from that vertex by following the DFS tree edges and, sometimes, a back edge.

That low-link idea is the heart of the method. If a vertex has a low-link value equal to its own discovery index, that vertex is the root of an SCC. At that moment, Tarjan's Algorithm pops vertices off a stack until it reaches that root, and all of those popped vertices belong to the same component.

The stack matters because not every visited vertex should be grouped together. Tarjan only keeps vertices on the stack while they are part of the current active DFS search path. When a component is finished, those vertices come off the stack, so later searches do not mix old components with new ones.

A small example makes the idea easier to see. Suppose you have directed edges A to B, B to C, and C back to A. Those three vertices form one SCC because each can reach the others. If D points to E but E cannot get back to D, then D and E are not in the same SCC. Tarjan's Algorithm separates those cases automatically instead of forcing you to check reachability from every vertex by hand.

In Combinatorics, this is a clean way to study how a directed graph breaks into mutually reachable pieces. The running time is O(V + E), which means it scans each vertex and edge only a small number of times. That makes it efficient enough for large graph problems, not just tiny examples on paper.

## Why It Matters

Tarjan's Algorithm matters because directed graphs are often easier to understand once you split them into SCCs. Instead of treating a whole graph as one messy structure, you can compress each SCC into a single node and study the bigger pattern of how those components connect.

That shows up a lot in graph theory problems where direction matters. A web of course dependencies, one-way roads, or state transitions may contain cycles that trap movement inside a component. Tarjan's Algorithm tells you exactly where those cycles live, which vertices are mutually reachable, and where the graph stops behaving like a loop.

It also connects directly to the chapter on graph connectivity and cut vertices. Even though SCCs are about directed graphs, the same general mindset appears in connectivity questions throughout Combinatorics: find the structural weak spots, separate the graph into meaningful pieces, and describe what happens when part of the graph is removed.

The algorithm is also a good example of how a clever bookkeeping trick beats brute force. Instead of checking reachability from every vertex to every other vertex, you use DFS, low-link values, and a stack to discover components in one pass. That pattern, turning a hard global question into a local traversal with memory, shows up again and again in graph algorithms.

## Connections

### Strongly Connected Component

Tarjan's Algorithm is built to find strongly connected components, so the component is the object and the algorithm is the method. If you do not know what an SCC is, the algorithm can feel random, because every step is really trying to detect one of those mutually reachable groups. Once you can spot SCCs, Tarjan's output makes much more sense.

### [Depth-First Search](/combinatorics/key-terms/depth-first-search)

DFS is the traversal Tarjan's Algorithm relies on. The algorithm uses the DFS tree to decide discovery order, and it uses the current recursion path to decide which vertices are still active on the stack. If you are shaky on DFS, Tarjan's low-link values and stack behavior can feel hard to track.

### Low-Link Value

Low-link values are the core measurement Tarjan uses to decide whether a vertex starts a new SCC. They tell you how far back in the DFS tree a vertex can connect, which is why they reveal cycles and component boundaries. Many mistakes come from updating low-link values too late or forgetting which edges are allowed to affect them.

### [Cut Edge](/combinatorics/key-terms/cut-edge)

Cut edges are more about undirected connectivity, but they belong to the same family of graph-separation ideas. Tarjan's Algorithm uses a different logic for directed graphs, yet both topics ask where a graph can break apart. If you are comparing them, focus on whether direction matters and whether the goal is components, bridges, or articulation points.

## On the AP Exam

A graph problem set usually asks you to trace Tarjan's Algorithm on a small directed graph, identify the DFS order, and mark when each vertex is popped from the stack. You may also need to compute low-link values by hand and explain why a set of vertices forms one strongly connected component.

When a question gives you a directed network, look for cycles first, because SCCs are the parts where every vertex can reach every other vertex. If you see a vertex whose low-link value matches its discovery index, that is a sign you found the root of a component. The common mistake is treating any cycle as one giant SCC without checking whether all vertices in the group can reach each other in both directions.

## Key Takeaways

- Tarjan's Algorithm finds strongly connected components in a directed graph using depth-first search.
- Each vertex gets a discovery index and a low-link value, and those values tell you when a component starts and ends.
- The stack stores the current active DFS path, so Tarjan can pop exactly the vertices that belong together.
- The algorithm runs in O(V + E) time, which makes it efficient for large graphs.
- In Combinatorics, Tarjan's Algorithm is a standard way to break a directed graph into mutually reachable pieces.

## FAQs

### What is Tarjan's Algorithm in Combinatorics?

Tarjan's Algorithm is a depth-first search algorithm for finding strongly connected components in a directed graph. It groups together vertices that can all reach one another by following directed edges. In Combinatorics, that makes it a fast way to analyze directed graph structure.

### How does Tarjan's Algorithm use low-link values?

Low-link values tell you the earliest discovery time a vertex can reach through the DFS path and back edges. If a vertex's low-link value matches its own discovery index, that vertex is the root of a strongly connected component. That is the signal Tarjan uses to start popping vertices from the stack.

### Why does Tarjan's Algorithm use a stack?

The stack keeps track of the vertices that are still part of the active DFS search path. When Tarjan finishes a strongly connected component, it pops exactly those vertices off the stack, so they are grouped together and not reused in later components. Without the stack, it would be much harder to tell which vertices still belong to the current component.

### Is Tarjan's Algorithm the same as BFS?

No. Tarjan's Algorithm is based on depth-first search, not breadth-first search. That matters because Tarjan needs the recursive DFS structure to compute low-link values and detect component roots. BFS explores level by level, which is useful for other graph tasks but not for this one.

## Related Study Guides

- [11.3 Graph connectivity and cut vertices](/combinatorics/unit-11/graph-connectivity-cut-vertices/study-guide/2VG4w4h0lorzd8Ay)

## About This Document

Canonical Fiveable pages are available as Markdown at the same path plus `.md`.

- [llms.txt](https://fiveable.me/llms.txt): index of Fiveable's sections and URL patterns
- [llms-full.txt](https://fiveable.me/llms-full.txt): complete subject and unit listing
- [MCP server](https://fiveable.me/mcp): call Fiveable as tools instead of fetching pages (`https://fiveable.me/api/mcp`)
- [MCP server for AP teachers](https://fiveable.me/mcp/teachers): a teacher's classes, assignments and AP-rubric grading (`https://fiveable.me/api/mcp/teacher`)

## Structured Data

```json
{"@context":"https://schema.org","@graph":[{"@type":"LearningResource","@id":"https://fiveable.me/combinatorics/key-terms/tarjans-algorithm#resource","name":"Tarjan's Algorithm in Combinatorics","url":"https://fiveable.me/combinatorics/key-terms/tarjans-algorithm","learningResourceType":"Concept explainer","educationalLevel":"AP® / High School","about":{"@id":"https://fiveable.me/combinatorics/key-terms/tarjans-algorithm#term"},"audience":{"@type":"EducationalAudience","educationalRole":"student"},"dateModified":"2026-07-03T02:21:06.613Z","isPartOf":{"@type":"Collection","name":"Combinatorics Key Terms","url":"https://fiveable.me/combinatorics/key-terms"},"publisher":{"@type":"Organization","name":"Fiveable","url":"https://fiveable.me"}},{"@type":"DefinedTerm","@id":"https://fiveable.me/combinatorics/key-terms/tarjans-algorithm#term","name":"Tarjan's Algorithm","description":"Tarjan's Algorithm is a depth-first search method for finding strongly connected components in a directed graph. In Combinatorics, it shows how graph connectivity can be broken into pieces in linear time.","url":"https://fiveable.me/combinatorics/key-terms/tarjans-algorithm","inDefinedTermSet":{"@type":"DefinedTermSet","name":"Combinatorics Key Terms","url":"https://fiveable.me/combinatorics/key-terms"}},{"@type":"FAQPage","mainEntity":[{"@type":"Question","name":"What is Tarjan's Algorithm in Combinatorics?","acceptedAnswer":{"@type":"Answer","text":"Tarjan's Algorithm is a depth-first search algorithm for finding strongly connected components in a directed graph. It groups together vertices that can all reach one another by following directed edges. In Combinatorics, that makes it a fast way to analyze directed graph structure."}},{"@type":"Question","name":"How does Tarjan's Algorithm use low-link values?","acceptedAnswer":{"@type":"Answer","text":"Low-link values tell you the earliest discovery time a vertex can reach through the DFS path and back edges. If a vertex's low-link value matches its own discovery index, that vertex is the root of a strongly connected component. That is the signal Tarjan uses to start popping vertices from the stack."}},{"@type":"Question","name":"Why does Tarjan's Algorithm use a stack?","acceptedAnswer":{"@type":"Answer","text":"The stack keeps track of the vertices that are still part of the active DFS search path. When Tarjan finishes a strongly connected component, it pops exactly those vertices off the stack, so they are grouped together and not reused in later components. Without the stack, it would be much harder to tell which vertices still belong to the current component."}},{"@type":"Question","name":"Is Tarjan's Algorithm the same as BFS?","acceptedAnswer":{"@type":"Answer","text":"No. Tarjan's Algorithm is based on depth-first search, not breadth-first search. That matters because Tarjan needs the recursive DFS structure to compute low-link values and detect component roots. BFS explores level by level, which is useful for other graph tasks but not for this one."}}]},{"@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"name":"Combinatorics","item":"https://fiveable.me/combinatorics"},{"@type":"ListItem","position":2,"name":"Key Terms","item":"https://fiveable.me/combinatorics/key-terms"},{"@type":"ListItem","position":3,"name":"Unit 11","item":"https://fiveable.me/combinatorics/unit-11"},{"@type":"ListItem","position":4,"name":"Tarjan's Algorithm"}]}]}
```