# automaton.scc(algo = "auto")¶

Compute the strongly-connected components and decorate the input automaton with them.

The algorithm can be:

• "auto": same as "tarjan".
• "dijkstra": Dijkstra's algorithm.
• "tarjan": Tarjan's algorithm implemented without recursion. Fast and robust to deep automata.
• "tarjan,recursive": Tarjan's algorithm implemented with recursion. Faster than "tarjan", but might explode on very deep automata.
• "kosaraju": Kosaraju's algorithm. Slower.

## Examples¶

In :
import vcsn
z = vcsn.context('lal_char(abc), z')

In :
a = z.expression('(<2>a<3>b)*').standard()
a

Out:

This automaton has two strongly connected components:

• Component 0: $\{0\}$
• Component 1: $\{1, 3\}$
In :
c = a.scc()
c

Out:
In :
c.is_isomorphic(a)

Out:
True

### scc.component(num)¶

To select a specific component, use component:

In :
c.component(0)

Out:
In :
c.component(1)

Out:

### scc.condense()¶

Or view the condensation (each strongly-connected component is reduced as a single state) of the automaton.

In :
c.condense()

Out:

### scc.num_components()¶

View number of strongly connected components:

In :
c.num_components()

Out:
2

The following automaton has 3 components.

In :
a = z.expression("(abc)*{2}").standard()
a

Out:

Using the recursive implementation of the Tarjan algorithm:

In :
c = a.scc("tarjan_recursive")
c

Out:
In :
c.is_isomorphic(a)

Out:
True
In :
c.component(1)

Out:
In :
c.condense()

Out:
In :
c.num_components()

Out:
3