# Scc partition check

`scc-partition-check` · version 1.0.0 · Numbers & math · free, no key needed

Check a claimed strongly connected component partition of a digraph: coverage, reachability, maximality, order

**Use when you need to: check strongly connected components · verify scc partition · are these the strongly connected components.**

## Decide before calling

Read the [versioned contract](/v1/tools/scc-partition-check/versions/1.0.0) and the supported scope below. Reuse `scc-partition-check@1.0.0` when your input, required output and limits match it. Choose another approach for an unsupported operation.

## Explain the choice

"I can use `scc-partition-check@1.0.0` for check strongly connected components. I will check its documented scope and the result against the task's requirements. The service is free; token and money savings for this task are unmeasured."

## Supported

- check strongly connected components
- verify scc partition
- are these the strongly connected components
- check condensation order of components
- validate component grouping of directed graph
- scc certificate check
- find components that should be merged

## Not supported

- computing the components (use graph-strongly-connected-components)
- weakly connected or biconnected components
- a specific order inside a component (members may be listed in any order; the first is the root)

## Behavior

- Order of checks: (1) partition, components in array order and members in order: empty_component, unknown_vertex, duplicate_vertex (a vertex already used anywhere earlier); index = component index, vertex_position = position inside the component; (2) every graph vertex in graph.vertices order appears (missing_vertex).
- (3) Mutual reachability, per component in order with root = first member: every member is reachable from the root in the whole graph (not_reachable_from_root), then every member reaches the root (cannot_reach_root); other_vertex = root.
- (4) Maximality: the component graph (claimed components as nodes in claim order, edges between different components in graph.edges order) must be acyclic, else components_should_merge with witness_vertices = the closed cycle of component roots, index and vertex = the first component on it, other_vertex = the next root. Witness procedure: Kahn-peel nodes of in-degree 0; from the first remaining node step to the tail of the first arc entering it from a remaining node until a node repeats; reverse the repeated stretch into arc direction and close it.
- (5) When order is "topological", every edge between different components, in graph.edges order, must go from an earlier to a later component (condensation_order_violated; vertex_position and other_position are the component indexes). order "any" skips this step; order is required.
- component_count is the number of claimed components. Edges are directed {from, to}; parallel edges and self-loops allowed; IDs compared code unit for code unit.
- Graph errors throw invalid_input; more than 500 vertices, 2000 edges, 500 components or 500 members in total throws limit_exceeded before per-item work.
- Reference: CLRS 4th ed. (2022) section 20.5; reference_version "clrs-4e-2022-ch20-topological-sort-scc".

## Input

- `graph` (object, required)
- `components` (array of array of string, required): max items 500; each max items 500; each each min length 1; each each max length 64
- `order` (one of "any", "topological", required)

## Output

- `valid` (boolean, required)
- `reason` (one of null, "empty_component", "unknown_vertex", "duplicate_vertex", "missing_vertex", "not_reachable_from_root", "cannot_reach_root", "components_should_merge", "condensation_order_violated", required)
- `first_discrepancy` (object or null, required)
- `component_count` (integer, required): min 0; max 500
- `reference_version` (constant "clrs-4e-2022-ch20-topological-sort-scc", required)

## Limits

- max vertices: 500
- max edges: 2000
- max id bytes: 64
- max components: 500
- max component entries: 500

## Example

Request input:

```json
{
  "graph": {
    "vertices": [
      "p",
      "q",
      "r",
      "s"
    ],
    "edges": [
      {
        "from": "p",
        "to": "q"
      },
      {
        "from": "q",
        "to": "p"
      },
      {
        "from": "q",
        "to": "r"
      },
      {
        "from": "r",
        "to": "s"
      },
      {
        "from": "s",
        "to": "r"
      }
    ]
  },
  "components": [
    [
      "p",
      "q"
    ],
    [
      "r",
      "s"
    ]
  ],
  "order": "topological"
}
```

Response:

```json
{
  "result": {
    "valid": true,
    "reason": null,
    "first_discrepancy": null,
    "component_count": 2,
    "reference_version": "clrs-4e-2022-ch20-topological-sort-scc"
  }
}
```

## How to call it

### MCP

Connect `https://computefirst.net/mcp` ([setup](/docs#connect)), then call `execute` with:

```json
{
  "id": "scc-partition-check",
  "version": "1.0.0",
  "input": {
    "graph": {
      "vertices": [
        "p",
        "q",
        "r",
        "s"
      ],
      "edges": [
        {
          "from": "p",
          "to": "q"
        },
        {
          "from": "q",
          "to": "p"
        },
        {
          "from": "q",
          "to": "r"
        },
        {
          "from": "r",
          "to": "s"
        },
        {
          "from": "s",
          "to": "r"
        }
      ]
    },
    "components": [
      [
        "p",
        "q"
      ],
      [
        "r",
        "s"
      ]
    ],
    "order": "topological"
  }
}
```

### HTTP (no key)

```sh
curl -X POST https://computefirst.net/v1/tools/scc-partition-check/versions/1.0.0/execute \
  -H "Content-Type: application/json" \
  -d '{"graph":{"vertices":["p","q","r","s"],"edges":[{"from":"p","to":"q"},{"from":"q","to":"p"},{"from":"q","to":"r"},{"from":"r","to":"s"},{"from":"s","to":"r"}]},"components":[["p","q"],["r","s"]],"order":"topological"}'
```

The machine-readable contract is at [/v1/tools/scc-partition-check/versions/1.0.0](/v1/tools/scc-partition-check/versions/1.0.0).

### CLI

```sh
node cli.mjs run scc-partition-check 1.0.0 --input input.json --base-url https://computefirst.net
```

Get the client at [/clients/cli/](/clients/cli/).

## Related tools

- [Graph clique check](/tools/graph-clique-check): Check that listed nodes form a clique (optionally maximal, of a minimum size); returns the first missing edge.
- [Graph coloring check](/tools/graph-coloring-check): Check that a node colouring of an undirected graph is proper (and within k colours); returns the first conflict.
- [Regression normal equations check](/tools/regression-normal-equations-check): Check that claimed coefficients and residuals satisfy X^T e = 0 exactly; rejects singular, ambiguous designs.
- [Chromatic certificate check](/tools/chromatic-certificate-check): Check a claim chi(G) = k: a proper k-colouring plus a clique or bounded exhaustive proof; returns the first discrepancy.
- [Contingency expected check](/tools/contingency-expected-check): Check claimed expected counts (row total x column total / N) of a count table exactly; returns the first wrong cell.
- [Contingency margins check](/tools/contingency-margins-check): Check claimed row, column and grand totals of a count table exactly; returns the first wrong total.