---
sources:
  - ../../src/analyses/scc.rs
---

# Strongly connected components

## The concept

A **strongly connected component** (SCC) is a maximal set of nodes where every node can reach every other node following edge directions. In other words, there is a directed cycle connecting all members.

```
SCC {a, b, c}                  Not an SCC

a ──→ b                        a ──→ b ──→ c
▲     │                        (c cannot reach a)
└──── c ◄─┘
```

A trivial SCC contains a single node with no self-loop. Non-trivial SCCs (size > 1, or a self-loop) indicate cyclic dependencies.

## Why it matters for knowledge systems

The existing `cycle` rule tells you a cycle exists. SCCs tell you **exactly which documents** are entangled in each cycle:

- **Refactoring guidance.** Knowing the exact set of files in a cycle tells you where to break the dependency. A 2-node cycle is easy to resolve; a 12-node cycle may indicate a deeper structural issue.
- **Impact understanding.** Changes to any file in an SCC can propagate to every other file in the same SCC. Larger SCCs have larger blast radii.
- **Structural health.** Many small SCCs may be acceptable; one large SCC spanning most of the graph usually signals that the document hierarchy has collapsed.

## What drft surfaces

### As an analysis (`drft report`)

```bash
drft report scc
```

```
=== scc ===
1 non-trivial SCC
scc 1 (3 nodes): a.md, b.md, c.md
```

For acyclic graphs:

```
=== scc ===
no non-trivial SCCs (graph is acyclic)
```

JSON output:

```json
{
  "scc": {
    "scc_count": 4,
    "nontrivial_count": 1,
    "sccs": [
      { "id": 1, "members": ["a.md", "b.md", "c.md"] }
    ],
    "node_scc": {
      "a.md": 1,
      "b.md": 1,
      "c.md": 1,
      "d.md": 2
    }
  }
}
```

`scc_count` includes trivial SCCs (single nodes). `nontrivial_count` and `sccs` only reflect SCCs with size > 1 or self-loops. `node_scc` maps every real node to its SCC ID.

## Algorithm

Uses [Tarjan's algorithm](https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm): a single DFS pass with a stack, maintaining discovery index and low-link values. When a node's low-link equals its index, the stack is popped to form an SCC. Only edges between real nodes are followed. Complexity is O(V + E).
