# Tarjan SCC / Bridge / Articulation-Point Graph Decomposer with Condensation Topological Order

Decompose a directed or undirected graph with Tarjan's 1972 iterative SCC algorithm cross-checked against Kosaraju's two-pass; find articulation points and bridges via low-links; build the condensation DAG with a Kahn topological order; report cycles (nodes on cycles, self-loops) and depth-limited BFS/DFS traversals.

> Canonical page: https://elysiatools.com/en/tools/tarjan-scc-tarjan-bridge-and-strongly-connected-components-topological-order-graph-decomposer

- **Category:** Development

- **Keywords:** tarjan, strongly connected components, kosaraju, articulation points, bridges, condensation, topological sort, cycle detection, graph algorithms, low-link

## Overview

Tarjan's SCC runs iteratively with an explicit stack (disc/low arrays, components collected on pop); Kosaraju orders vertices by iterative finish time then collects on the reversed graph — both must agree component-for-component (mutual verification). Bridges and articulation points use low-links on the undirected view: low[v] > disc[u] means a bridge; a root with ≥2 subtree children or low[v] ≥ disc[u] means an articulation point. The condensation builds a DAG over components ordered by Kahn's in-degree method; the original graph admits a full topological order iff acyclic (nodes on cycles counted as SCCs of size > 1 plus self-loops). BFS proceeds layer by layer, DFS with an explicit stack; both honor the depth limit. All passes are O(V+E).

## Inputs

- **Graph (edge list or adjacency, one per line)** (textarea): a -> b b -> c c -> a d -> c
- **Directed graph** (checkbox)
- **Traversal start node** (text): a
- **Max traversal depth** (number): 4

## When to use

- Analyzing software package dependency graphs or microservices to detect circular dependencies and compute valid build orders.
- Identifying critical single points of failure in network topologies through articulation points and bridge cuts.
- Studying or debugging graph theory algorithms, verifying SCC outputs against Kosaraju's two-pass algorithm, and inspecting condensation DAGs.

## How it works

- Parses the input edge list or adjacency representation into an internal graph model with directed or undirected edge semantics.
- Executes iterative Tarjan's SCC and Kosaraju's two-pass algorithms simultaneously to find and cross-verify all strongly connected components.
- Calculates low-link and discovery values across the undirected graph structure to detect articulation points and bridge edges.
- Constructs the condensation DAG over component representatives, applies Kahn's algorithm for topological sorting, and computes depth-bounded BFS and DFS trees from the chosen start node.

## Use cases

- Dependency management: Resolve circular imports and determine compilation or execution sequences using condensation DAG topological sorting.
- Network vulnerability assessment: Identify critical routers (articulation points) and transmission lines (bridges) whose removal partitions the infrastructure.
- Algorithm education and validation: Verify manual low-link, discovery time, and SCC decomposition calculations against deterministic implementations.

## Frequently asked questions

### What graph input formats are accepted?

You can provide edge lists (such as 'a -> b' or 'a b') or adjacency lists (such as 'a: b c'), with one record per line.

### How are Tarjan's and Kosaraju's algorithms cross-checked?

Tarjan's iterative stack-based algorithm and Kosaraju's two-pass finish-time algorithm run independently and must yield matching components for verification.

### How are bridges and articulation points determined?

They are identified on the undirected graph view using low-link and discovery times: low[v] > disc[u] marks a bridge, and low[v] >= disc[u] (or a root with multiple children) marks an articulation point.

### Can the tool perform a full topological sort on graphs with cycles?

A full topological sort is only valid on acyclic graphs, but the tool will always produce a valid Kahn topological order on the condensed DAG of components.

### What does the maximum depth setting control?

It restricts the layer depth reached during breadth-first search (BFS) and explicit-stack depth-first search (DFS) traversals starting from the specified start node.

## Related tools

- [Cron Expression Visualizer](https://elysiatools.com/en/tools/cron-expression-visualizer): Parse cron schedules, validate standard or Quartz syntax, and visualize the next execution times on a timeline and grouped calendar view
- [Tailwind Color Palette Sync](https://elysiatools.com/en/tools/tailwind-color-palette-sync): Generate theme.extend.colors for tailwind.config.ts from HEX colors, with WCAG contrast levels and optional dark mode.
- [Cron Expression Explainer](https://elysiatools.com/en/tools/cron-expression-explainer): Parse a 5-part / 6-part / Quartz cron expression into a plain-language schedule description, show the field-by-field breakdown, and list the next N execution times in any IANA timezone — with an AI-generated natural-language explanation in your language
- [Cron Job Simulator](https://elysiatools.com/en/tools/cron-job-simulator): Simulate the next runs of one or two 5-part cron expressions, highlight overlaps, and warn about overly dense schedules
- [API Contract Mutation Tester](https://elysiatools.com/en/tools/api-contract-mutation-tester): Mutate OpenAPI request fields into semantically risky variants and optionally send them to a real backend to check defensive validation coverage
- [CSV Malformed Row Surgeon](https://elysiatools.com/en/tools/csv-malformed-row-surgeon): Surgically repair malformed CSV rows one at a time: unescaped (stray) quotes, mixed delimiters (tab/semicolon/comma in the same file), BOM-prefixed headers, CRLF/CR line endings and trailing empty lines. The surgeon parses tolerantly, shows a row-level red/green diff of every change it made (before → after, with the repair reason tagged), lists the rows it accepted unchanged, and emits the cleaned CSV. Optional AI repair can review suspicious rows after the deterministic pass. It complements the CSV Validator (which only reports problems) by actually fixing the damaged rows.
- [OAuth 2.0 / OIDC Authorization Code with PKCE Flow Visualizer](https://elysiatools.com/en/tools/oauth-oidc-authorization-code-pkce-flow-visualizer): Simulate the Authorization Code flow with PKCE end to end: verifier/challenge generation, authorization URL, token exchange, ID Token validation checklist and an interception-attack demo.
- [Responsive Picture / srcset Art Direction Builder](https://elysiatools.com/en/tools/responsive-picture-srcset-art-direction-builder): Build complete markup with art-directed crops: per-breakpoint elements, 1x/2x density candidates or {w}-template width descriptors, optional AVIF/WebP format layers, sizes handling, CLS-safe width/height, plus HTML and JSX flavors with spec-based lint notes.

## Samples

- [Copyright-Free FLAC Audio Samples](https://elysiatools.com/en/samples/flac-samples): Lossless FLAC audio samples for testing and development, mirrored from MP3 set with nature sounds and meditation music
- [Copyright-Free WAV Audio Samples](https://elysiatools.com/en/samples/wav-samples): Uncompressed PCM WAV audio samples for testing and development, mirrored from MP3 set with nature sounds and meditation music
- [Android Image Processing Java Samples](https://elysiatools.com/en/samples/android-image-processing-java): Android Java image processing examples including reading/saving images, scaling, and format conversion
- [Android Image Processing Kotlin Samples](https://elysiatools.com/en/samples/android-image-processing-kotlin): Android Kotlin image processing examples including reading/saving images, scaling, and format conversion