38.01Intermediate / Advanced5 topics16 min5 interactive animations

DFS timestamps

Give every vertex an entry and exit time during a DFS and track the low-link value: with these three numbers bridges, cut vertices and strongly connected components all fall out of one traversal.

Learning goals

Compute tin, tout and low for every vertex of an undirected graph
Classify each edge as a tree edge or a back edge
Explain why the parent edge is skipped by edge id, not by vertex
Use the nesting of [tin, tout] intervals to test ancestry

Prerequisites

Depth-first searchAdjacency listsRecursion

Imagine walking through a cave system with a ball of string and writing the time you first enter and finally leave every chamber. Those times tell you, later, which chambers lie inside which, and the string you left behind shows whether any tunnel loops back above you.

38.01.1

tin and tout

A depth-first search visits each vertex once. Keep a counter timer. When DFS first reaches u, set tin[u] = ++timer; when it has finished all of u's neighbours, set tout[u] = ++timer. The pair [tin[u], tout[u]] is the time u spent on the recursion stack.

Intervals nest like brackets: if v is visited while u is still open, then [tin[v], tout[v]] lies inside [tin[u], tout[u]]. That gives an O(1) ancestor test: a is an ancestor of b exactly when tin[a] <= tin[b] and tout[b] <= tout[a].

Because the timer ticks twice per vertex, a vertex whose subtree has s vertices spans 2s ticks, so s = (tout - tin + 1) / 2. On the “Triangle with a tail” preset (edges 0-1 1-2 2-0 2-3 3-4, start 0) the times are tin = 1 2 3 4 5 and tout = 10 9 8 7 6: vertex 0 spans the whole walk, vertex 4 only one pair of ticks.

Java

1static class Dfs {
2    int timer = 0;
3    int[] tin, tout, low, parentEdge;                   // tin 0 means "not visited yet"
4    List<int[]>[] g;                                    // g[u] holds {neighbour, edge id}
5
6    @SuppressWarnings("unchecked")
7    Dfs(int n, int[][] edges) {
8        tin = new int[n]; tout = new int[n]; low = new int[n]; parentEdge = new int[n];
9        Arrays.fill(parentEdge, -1);
10        g = new List[n];
11        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
12        for (int k = 0; k < edges.length; k++) {
13            g[edges[k][0]].add(new int[]{edges[k][1], k});
14            g[edges[k][1]].add(new int[]{edges[k][0], k});
15        }
16    }
17
18    void run(int start) {                               // start first, then any vertex still unvisited
19        dfs(start, -1);
20        for (int v = 0; v < tin.length; v++) if (tin[v] == 0) dfs(v, -1);
21    }
22
23    void dfs(int u, int pe) {
24        tin[u] = low[u] = ++timer;
25        for (int[] e : g[u]) {
26            int v = e[0], id = e[1];
27            if (id == pe) continue;                     // skip the edge we came by (by id)
28            if (tin[v] != 0) {
29                low[u] = Math.min(low[u], tin[v]);      // back edge
30            } else {
31                parentEdge[v] = id;                     // tree edge
32                dfs(v, id);
33                low[u] = Math.min(low[u], low[v]);
34            }
35        }
36        tout[u] = ++timer;
37    }
38}
39
40static int[][] timestamps(int n, int[][] edges, int start) {   // {tin, tout, low}
41    Dfs d = new Dfs(n, edges);
42    d.run(start);
43    return new int[][]{d.tin, d.tout, d.low};
44}

Worst

O(n + m)

Space

O(n) for the arrays and the recursion

DFS timestamps: tin, tout, low-link, tree and back edges

Interactive · edit the input

node caption: tin / tout · 5 vertices · 5 edges

Current vertex or edgeOpen vertex, or back edge (B)Finished vertex, or tree edge (T)

tin

–0

–1

–2

–3

–4

tout

–0

–1

–2

–3

–4

low

–0

–1

–2

–3

–4

Setup

5 vertices and 5 edges. DFS starts at 0. It gives every vertex an entry time tin when first reached and an exit time tout when finished, and tracks low: the smallest entry time reachable from the subtree using tree edges downwards and at most one back edge.

Step 1 / 27

Java

1static int timer = 0;
2static int[] tin, tout, low;                          // tin 0 means "not visited yet"
3static void dfs(List<int[]>[] g, int u, int parentEdge) {   // g[u] holds {neighbour, edge id}
4    tin[u] = low[u] = ++timer;                        // entry time; low starts as its own entry time
5    for (int[] e : g[u]) {
6        int v = e[0], id = e[1];
7        if (id == parentEdge) continue;               // skip the edge we came by: by id, so a parallel copy still counts
8        if (tin[v] != 0) {                            // already visited
9            low[u] = Math.min(low[u], tin[v]);        // back edge to an ancestor (from an ancestor's side it changes nothing)
10        } else {
11            dfs(g, v, id);                            // tree edge: v is a new child
12            low[u] = Math.min(low[u], low[v]);        // whatever v's subtree reaches, u reaches
13        }
14    }
15    tout[u] = ++timer;                                // exit time: [tin, tout] nests like brackets
16}

Live state

0 tree edges0 back edges

edges

No condition evaluated on this step

Execution trace (dry run table)Show 27 steps

Step	Line	State	What happens
1	L1	n=5 edges=5	5 vertices and 5 edges. DFS starts at 0. It gives every vertex an entry time tin when first reached and an exit time tout when finished, and tracks low: the smallest entry time reachable from the subtree using tree edges downwards and at most one back edge.
2	L1	root=0	0 has not been visited, so start a new DFS tree here.
3	L4	u=0 tin=1 low=1	Enter 0: tin[0] = 1 and low[0] starts equal to it.
4	L11	u=0 v=1	1 is new: 0-1 becomes a tree edge and DFS goes down into 1.
5	L4	u=1 tin=2 low=2	Enter 1: tin[1] = 2 and low[1] starts equal to it.
6	L7	u=1 edge=0-1	Edge 0-1 is the one DFS used to reach 1; skip it by id. (A parallel copy of this edge would not be skipped.)
7	L11	u=1 v=2	2 is new: 1-2 becomes a tree edge and DFS goes down into 2.
8	L4	u=2 tin=3 low=3	Enter 2: tin[2] = 3 and low[2] starts equal to it.
9	L7	u=2 edge=1-2	Edge 1-2 is the one DFS used to reach 2; skip it by id. (A parallel copy of this edge would not be skipped.)
10	L9	u=2 v=0 tin_v=1 low=1	0 is visited and older (tin 1 < tin 3): 2-0 is a back edge up to an ancestor. low[2] drops from 3 to 1.
11	L11	u=2 v=3	3 is new: 2-3 becomes a tree edge and DFS goes down into 3.
12	L4	u=3 tin=4 low=4	Enter 3: tin[3] = 4 and low[3] starts equal to it.
13	L7	u=3 edge=2-3	Edge 2-3 is the one DFS used to reach 3; skip it by id. (A parallel copy of this edge would not be skipped.)
14	L11	u=3 v=4	4 is new: 3-4 becomes a tree edge and DFS goes down into 4.
15	L4	u=4 tin=5 low=5	Enter 4: tin[4] = 5 and low[4] starts equal to it.
16	L7	u=4 edge=3-4	Edge 3-4 is the one DFS used to reach 4; skip it by id. (A parallel copy of this edge would not be skipped.)
17	L15	u=4 tin=5 tout=6	4 is finished: tout[4] = 6. The interval [5, 6] contains the intervals of all of 4's descendants.
18	L12	u=3 v=4 low_v=5 low=4	Back at 3 from 4: low[4] = 5, so low[3] stays 4.
19	L15	u=3 tin=4 tout=7	3 is finished: tout[3] = 7. The interval [4, 7] contains the intervals of all of 3's descendants.
20	L12	u=2 v=3 low_v=4 low=1	Back at 2 from 3: low[3] = 4, so low[2] stays 1.
21	L15	u=2 tin=3 tout=8	2 is finished: tout[2] = 8. The interval [3, 8] contains the intervals of all of 2's descendants.
22	L12	u=1 v=2 low_v=1 low=1	Back at 1 from 2: low[2] = 1, so low[1] drops from 2 to 1.
23	L15	u=1 tin=2 tout=9	1 is finished: tout[1] = 9. The interval [2, 9] contains the intervals of all of 1's descendants.
24	L12	u=0 v=1 low_v=1 low=1	Back at 0 from 1: low[1] = 1, so low[0] stays 1.
25	L8	u=0 v=2	2 is already visited and younger: 2-0 is the same back edge seen from its upper end, and it was counted from 2. Min with tin[2] = 3 cannot lower low[0].
26	L15	u=0 tin=1 tout=10	0 is finished: tout[0] = 10. The interval [1, 10] contains the intervals of all of 0's descendants.
27	L15	return=1 tree_edges=4 back_edges=1	Done: 4 tree edges (n minus the number of DFS trees) and 1 back edge. Every non-tree edge of an undirected DFS joins an ancestor and a descendant.

38.01.2

Low-link value

low[u] is the smallest entry time that u's subtree can reach by going down tree edges and then using at most one back edge. Start with low[u] = tin[u]. Two rules lower it: a back edge from u to an already visited vertex v gives low[u] = min(low[u], tin[v]), and after returning from a child v you take low[u] = min(low[u], low[v]).

Read it as “how far up the tree can this subtree climb”. On the “Triangle with a tail” preset the result is low = 1 1 1 4 5: the cycle 0-1-2 lets vertices 1 and 2 climb to vertex 0 (entry time 1), while 3 and 4 hang off a single edge and can only reach themselves. Start the same graph at the tail instead (the “Same graph, start at the tail” preset) and the numbers change to tin = 5 4 3 2 1, low = 3 3 3 2 1: low values depend on the DFS, but the conclusions drawn from them do not.

The code below recomputes low straight from its definition, a slow O(n·m) loop, so you can cross-check the DFS. A vertex w is in the subtree of u when its interval nests inside u's; every edge leaving such a vertex except its own parent edge contributes the entry time of the other end.

Java

1static int[] lowByDefinition(int n, int[][] edges, int[] tin, int[] tout, int[] parentEdge) {
2    int[] low = new int[n];
3    for (int u = 0; u < n; u++) {
4        low[u] = tin[u];
5        for (int k = 0; k < edges.length; k++) {
6            for (int side = 0; side < 2; side++) {
7                int w = edges[k][side], x = edges[k][1 - side];
8                boolean inSubtree = tin[u] <= tin[w] && tout[w] <= tout[u];
9                if (inSubtree && k != parentEdge[w]) low[u] = Math.min(low[u], tin[x]);
10            }
11        }
12    }
13    return low;
14}

DFS timestamps: tin, tout, low-link, tree and back edges

Interactive · edit the input

node caption: tin / tout · 5 vertices · 5 edges

Current vertex or edgeOpen vertex, or back edge (B)Finished vertex, or tree edge (T)

tin

–0

–1

–2

–3

–4

tout

–0

–1

–2

–3

–4

low

–0

–1

–2

–3

–4

Setup

Step 1 / 27

Java

1static int timer = 0;
2static int[] tin, tout, low;                          // tin 0 means "not visited yet"
3static void dfs(List<int[]>[] g, int u, int parentEdge) {   // g[u] holds {neighbour, edge id}
4    tin[u] = low[u] = ++timer;                        // entry time; low starts as its own entry time
5    for (int[] e : g[u]) {
6        int v = e[0], id = e[1];
7        if (id == parentEdge) continue;               // skip the edge we came by: by id, so a parallel copy still counts
8        if (tin[v] != 0) {                            // already visited
9            low[u] = Math.min(low[u], tin[v]);        // back edge to an ancestor (from an ancestor's side it changes nothing)
10        } else {
11            dfs(g, v, id);                            // tree edge: v is a new child
12            low[u] = Math.min(low[u], low[v]);        // whatever v's subtree reaches, u reaches
13        }
14    }
15    tout[u] = ++timer;                                // exit time: [tin, tout] nests like brackets
16}

Live state

0 tree edges0 back edges

edges

No condition evaluated on this step

Execution trace (dry run table)Show 27 steps

Step	Line	State	What happens
1	L1	n=5 edges=5	5 vertices and 5 edges. DFS starts at 0. It gives every vertex an entry time tin when first reached and an exit time tout when finished, and tracks low: the smallest entry time reachable from the subtree using tree edges downwards and at most one back edge.
2	L1	root=0	0 has not been visited, so start a new DFS tree here.
3	L4	u=0 tin=1 low=1	Enter 0: tin[0] = 1 and low[0] starts equal to it.
4	L11	u=0 v=1	1 is new: 0-1 becomes a tree edge and DFS goes down into 1.
5	L4	u=1 tin=2 low=2	Enter 1: tin[1] = 2 and low[1] starts equal to it.
6	L7	u=1 edge=0-1	Edge 0-1 is the one DFS used to reach 1; skip it by id. (A parallel copy of this edge would not be skipped.)
7	L11	u=1 v=2	2 is new: 1-2 becomes a tree edge and DFS goes down into 2.
8	L4	u=2 tin=3 low=3	Enter 2: tin[2] = 3 and low[2] starts equal to it.
9	L7	u=2 edge=1-2	Edge 1-2 is the one DFS used to reach 2; skip it by id. (A parallel copy of this edge would not be skipped.)
10	L9	u=2 v=0 tin_v=1 low=1	0 is visited and older (tin 1 < tin 3): 2-0 is a back edge up to an ancestor. low[2] drops from 3 to 1.
11	L11	u=2 v=3	3 is new: 2-3 becomes a tree edge and DFS goes down into 3.
12	L4	u=3 tin=4 low=4	Enter 3: tin[3] = 4 and low[3] starts equal to it.
13	L7	u=3 edge=2-3	Edge 2-3 is the one DFS used to reach 3; skip it by id. (A parallel copy of this edge would not be skipped.)
14	L11	u=3 v=4	4 is new: 3-4 becomes a tree edge and DFS goes down into 4.
15	L4	u=4 tin=5 low=5	Enter 4: tin[4] = 5 and low[4] starts equal to it.
16	L7	u=4 edge=3-4	Edge 3-4 is the one DFS used to reach 4; skip it by id. (A parallel copy of this edge would not be skipped.)
17	L15	u=4 tin=5 tout=6	4 is finished: tout[4] = 6. The interval [5, 6] contains the intervals of all of 4's descendants.
18	L12	u=3 v=4 low_v=5 low=4	Back at 3 from 4: low[4] = 5, so low[3] stays 4.
19	L15	u=3 tin=4 tout=7	3 is finished: tout[3] = 7. The interval [4, 7] contains the intervals of all of 3's descendants.
20	L12	u=2 v=3 low_v=4 low=1	Back at 2 from 3: low[3] = 4, so low[2] stays 1.
21	L15	u=2 tin=3 tout=8	2 is finished: tout[2] = 8. The interval [3, 8] contains the intervals of all of 2's descendants.
22	L12	u=1 v=2 low_v=1 low=1	Back at 1 from 2: low[2] = 1, so low[1] drops from 2 to 1.
23	L15	u=1 tin=2 tout=9	1 is finished: tout[1] = 9. The interval [2, 9] contains the intervals of all of 1's descendants.
24	L12	u=0 v=1 low_v=1 low=1	Back at 0 from 1: low[1] = 1, so low[0] stays 1.
25	L8	u=0 v=2	2 is already visited and younger: 2-0 is the same back edge seen from its upper end, and it was counted from 2. Min with tin[2] = 3 cannot lower low[0].
26	L15	u=0 tin=1 tout=10	0 is finished: tout[0] = 10. The interval [1, 10] contains the intervals of all of 0's descendants.
27	L15	return=1 tree_edges=4 back_edges=1	Done: 4 tree edges (n minus the number of DFS trees) and 1 back edge. Every non-tree edge of an undirected DFS joins an ancestor and a descendant.

38.01.3

Back edges

After the DFS every edge is either a **tree edge** (used to discover a new vertex) or a **back edge**. In an undirected graph there is no third kind: a non-tree edge cannot join two unrelated branches, because DFS would have walked it before leaving the first branch. So every back edge joins an ancestor and a descendant.

The edge appears twice in the adjacency lists. Seen from the descendant, the other end is an old vertex with a smaller tin: that is where low is lowered. Seen from the ancestor, the other end is a younger vertex that is already finished; the min with its larger tin changes nothing, which is why the code can use a single tin[v] != 0 branch.

Count them: a DFS forest over n vertices with c trees has n - c tree edges, so a graph with m edges has m - n + c back edges. The “A square with a chord” preset (0-1 1-2 2-3 3-0 0-2) has 3 tree edges and 2 back edges. Step through it and watch the second sighting of each back edge, labelled in the log as the same edge seen from above.

Java

1static char[] edgeKinds(int n, int[][] edges, int start) {   // 'T' tree edge, 'B' back edge, one letter per edge id
2    Dfs d = new Dfs(n, edges);
3    d.run(start);
4    char[] kind = new char[edges.length];
5    Arrays.fill(kind, 'B');
6    for (int v = 0; v < n; v++) if (d.parentEdge[v] != -1) kind[d.parentEdge[v]] = 'T';
7    return kind;
8}
9
10static boolean isAncestor(int[] tin, int[] tout, int a, int b) {   // a is b or lies above b in the DFS tree
11    return tin[a] <= tin[b] && tout[b] <= tout[a];
12}

DFS timestamps: tin, tout, low-link, tree and back edges

Interactive · edit the input

node caption: tin / tout · 5 vertices · 5 edges

Current vertex or edgeOpen vertex, or back edge (B)Finished vertex, or tree edge (T)

tin

–0

–1

–2

–3

–4

tout

–0

–1

–2

–3

–4

low

–0

–1

–2

–3

–4

Setup

Step 1 / 27

Java

1static int timer = 0;
2static int[] tin, tout, low;                          // tin 0 means "not visited yet"
3static void dfs(List<int[]>[] g, int u, int parentEdge) {   // g[u] holds {neighbour, edge id}
4    tin[u] = low[u] = ++timer;                        // entry time; low starts as its own entry time
5    for (int[] e : g[u]) {
6        int v = e[0], id = e[1];
7        if (id == parentEdge) continue;               // skip the edge we came by: by id, so a parallel copy still counts
8        if (tin[v] != 0) {                            // already visited
9            low[u] = Math.min(low[u], tin[v]);        // back edge to an ancestor (from an ancestor's side it changes nothing)
10        } else {
11            dfs(g, v, id);                            // tree edge: v is a new child
12            low[u] = Math.min(low[u], low[v]);        // whatever v's subtree reaches, u reaches
13        }
14    }
15    tout[u] = ++timer;                                // exit time: [tin, tout] nests like brackets
16}

Live state

0 tree edges0 back edges

edges

No condition evaluated on this step

Execution trace (dry run table)Show 27 steps

Step	Line	State	What happens
1	L1	n=5 edges=5	5 vertices and 5 edges. DFS starts at 0. It gives every vertex an entry time tin when first reached and an exit time tout when finished, and tracks low: the smallest entry time reachable from the subtree using tree edges downwards and at most one back edge.
2	L1	root=0	0 has not been visited, so start a new DFS tree here.
3	L4	u=0 tin=1 low=1	Enter 0: tin[0] = 1 and low[0] starts equal to it.
4	L11	u=0 v=1	1 is new: 0-1 becomes a tree edge and DFS goes down into 1.
5	L4	u=1 tin=2 low=2	Enter 1: tin[1] = 2 and low[1] starts equal to it.
6	L7	u=1 edge=0-1	Edge 0-1 is the one DFS used to reach 1; skip it by id. (A parallel copy of this edge would not be skipped.)
7	L11	u=1 v=2	2 is new: 1-2 becomes a tree edge and DFS goes down into 2.
8	L4	u=2 tin=3 low=3	Enter 2: tin[2] = 3 and low[2] starts equal to it.
9	L7	u=2 edge=1-2	Edge 1-2 is the one DFS used to reach 2; skip it by id. (A parallel copy of this edge would not be skipped.)
10	L9	u=2 v=0 tin_v=1 low=1	0 is visited and older (tin 1 < tin 3): 2-0 is a back edge up to an ancestor. low[2] drops from 3 to 1.
11	L11	u=2 v=3	3 is new: 2-3 becomes a tree edge and DFS goes down into 3.
12	L4	u=3 tin=4 low=4	Enter 3: tin[3] = 4 and low[3] starts equal to it.
13	L7	u=3 edge=2-3	Edge 2-3 is the one DFS used to reach 3; skip it by id. (A parallel copy of this edge would not be skipped.)
14	L11	u=3 v=4	4 is new: 3-4 becomes a tree edge and DFS goes down into 4.
15	L4	u=4 tin=5 low=5	Enter 4: tin[4] = 5 and low[4] starts equal to it.
16	L7	u=4 edge=3-4	Edge 3-4 is the one DFS used to reach 4; skip it by id. (A parallel copy of this edge would not be skipped.)
17	L15	u=4 tin=5 tout=6	4 is finished: tout[4] = 6. The interval [5, 6] contains the intervals of all of 4's descendants.
18	L12	u=3 v=4 low_v=5 low=4	Back at 3 from 4: low[4] = 5, so low[3] stays 4.
19	L15	u=3 tin=4 tout=7	3 is finished: tout[3] = 7. The interval [4, 7] contains the intervals of all of 3's descendants.
20	L12	u=2 v=3 low_v=4 low=1	Back at 2 from 3: low[3] = 4, so low[2] stays 1.
21	L15	u=2 tin=3 tout=8	2 is finished: tout[2] = 8. The interval [3, 8] contains the intervals of all of 2's descendants.
22	L12	u=1 v=2 low_v=1 low=1	Back at 1 from 2: low[2] = 1, so low[1] drops from 2 to 1.
23	L15	u=1 tin=2 tout=9	1 is finished: tout[1] = 9. The interval [2, 9] contains the intervals of all of 1's descendants.
24	L12	u=0 v=1 low_v=1 low=1	Back at 0 from 1: low[1] = 1, so low[0] stays 1.
25	L8	u=0 v=2	2 is already visited and younger: 2-0 is the same back edge seen from its upper end, and it was counted from 2. Min with tin[2] = 3 cannot lower low[0].
26	L15	u=0 tin=1 tout=10	0 is finished: tout[0] = 10. The interval [1, 10] contains the intervals of all of 0's descendants.
27	L15	return=1 tree_edges=4 back_edges=1	Done: 4 tree edges (n minus the number of DFS trees) and 1 back edge. Every non-tree edge of an undirected DFS joins an ancestor and a descendant.

38.01.4

Tree edges

The tree edges form a spanning forest: one DFS tree per connected component. Store the edge id that discovered each vertex in parentEdge[v] (or -1 for a root); the set of those ids is exactly the set of tree edges.

Timestamps also give subtree sizes for free. With the double tick, size[v] = (tout[v] - tin[v] + 1) / 2. Many tree algorithms (counting descendants, lowest common ancestors by Euler tour) start from exactly this forest.

The forest depends on the order of the adjacency lists and on the start vertex. Run the “Parallel edges” preset from vertex 0 and the tree is the path 0-1-2; rerun the “Same graph, start at the tail” preset and the tree is rooted at 4 instead. Do not rely on a particular tree shape, only on the properties that hold for every DFS.

Property	Value for n vertices, m edges, c components
Tree edges	n − c
Back edges	m − n + c
Subtree size of v	(tout − tin + 1) / 2
Ancestor test	tin[a] ≤ tin[b] and tout[b] ≤ tout[a]

Java

1static List<Integer> treeEdgeIds(int n, int[][] edges, int start) {
2    Dfs d = new Dfs(n, edges);
3    d.run(start);
4    List<Integer> ids = new ArrayList<>();
5    for (int v = 0; v < n; v++) if (d.parentEdge[v] != -1) ids.add(d.parentEdge[v]);
6    return ids;
7}
8
9static int[] subtreeSizes(int[] tin, int[] tout) {    // the timer ticks twice per vertex
10    int[] size = new int[tin.length];
11    for (int v = 0; v < tin.length; v++) size[v] = (tout[v] - tin[v] + 1) / 2;
12    return size;
13}

DFS timestamps: tin, tout, low-link, tree and back edges

Interactive · edit the input

node caption: tin / tout · 5 vertices · 5 edges

Current vertex or edgeOpen vertex, or back edge (B)Finished vertex, or tree edge (T)

tin

–0

–1

–2

–3

–4

tout

–0

–1

–2

–3

–4

low

–0

–1

–2

–3

–4

Setup

Step 1 / 27

Java

1static int timer = 0;
2static int[] tin, tout, low;                          // tin 0 means "not visited yet"
3static void dfs(List<int[]>[] g, int u, int parentEdge) {   // g[u] holds {neighbour, edge id}
4    tin[u] = low[u] = ++timer;                        // entry time; low starts as its own entry time
5    for (int[] e : g[u]) {
6        int v = e[0], id = e[1];
7        if (id == parentEdge) continue;               // skip the edge we came by: by id, so a parallel copy still counts
8        if (tin[v] != 0) {                            // already visited
9            low[u] = Math.min(low[u], tin[v]);        // back edge to an ancestor (from an ancestor's side it changes nothing)
10        } else {
11            dfs(g, v, id);                            // tree edge: v is a new child
12            low[u] = Math.min(low[u], low[v]);        // whatever v's subtree reaches, u reaches
13        }
14    }
15    tout[u] = ++timer;                                // exit time: [tin, tout] nests like brackets
16}

Live state

0 tree edges0 back edges

edges

No condition evaluated on this step

Execution trace (dry run table)Show 27 steps

Step	Line	State	What happens
1	L1	n=5 edges=5	5 vertices and 5 edges. DFS starts at 0. It gives every vertex an entry time tin when first reached and an exit time tout when finished, and tracks low: the smallest entry time reachable from the subtree using tree edges downwards and at most one back edge.
2	L1	root=0	0 has not been visited, so start a new DFS tree here.
3	L4	u=0 tin=1 low=1	Enter 0: tin[0] = 1 and low[0] starts equal to it.
4	L11	u=0 v=1	1 is new: 0-1 becomes a tree edge and DFS goes down into 1.
5	L4	u=1 tin=2 low=2	Enter 1: tin[1] = 2 and low[1] starts equal to it.
6	L7	u=1 edge=0-1	Edge 0-1 is the one DFS used to reach 1; skip it by id. (A parallel copy of this edge would not be skipped.)
7	L11	u=1 v=2	2 is new: 1-2 becomes a tree edge and DFS goes down into 2.
8	L4	u=2 tin=3 low=3	Enter 2: tin[2] = 3 and low[2] starts equal to it.
9	L7	u=2 edge=1-2	Edge 1-2 is the one DFS used to reach 2; skip it by id. (A parallel copy of this edge would not be skipped.)
10	L9	u=2 v=0 tin_v=1 low=1	0 is visited and older (tin 1 < tin 3): 2-0 is a back edge up to an ancestor. low[2] drops from 3 to 1.
11	L11	u=2 v=3	3 is new: 2-3 becomes a tree edge and DFS goes down into 3.
12	L4	u=3 tin=4 low=4	Enter 3: tin[3] = 4 and low[3] starts equal to it.
13	L7	u=3 edge=2-3	Edge 2-3 is the one DFS used to reach 3; skip it by id. (A parallel copy of this edge would not be skipped.)
14	L11	u=3 v=4	4 is new: 3-4 becomes a tree edge and DFS goes down into 4.
15	L4	u=4 tin=5 low=5	Enter 4: tin[4] = 5 and low[4] starts equal to it.
16	L7	u=4 edge=3-4	Edge 3-4 is the one DFS used to reach 4; skip it by id. (A parallel copy of this edge would not be skipped.)
17	L15	u=4 tin=5 tout=6	4 is finished: tout[4] = 6. The interval [5, 6] contains the intervals of all of 4's descendants.
18	L12	u=3 v=4 low_v=5 low=4	Back at 3 from 4: low[4] = 5, so low[3] stays 4.
19	L15	u=3 tin=4 tout=7	3 is finished: tout[3] = 7. The interval [4, 7] contains the intervals of all of 3's descendants.
20	L12	u=2 v=3 low_v=4 low=1	Back at 2 from 3: low[3] = 4, so low[2] stays 1.
21	L15	u=2 tin=3 tout=8	2 is finished: tout[2] = 8. The interval [3, 8] contains the intervals of all of 2's descendants.
22	L12	u=1 v=2 low_v=1 low=1	Back at 1 from 2: low[2] = 1, so low[1] drops from 2 to 1.
23	L15	u=1 tin=2 tout=9	1 is finished: tout[1] = 9. The interval [2, 9] contains the intervals of all of 1's descendants.
24	L12	u=0 v=1 low_v=1 low=1	Back at 0 from 1: low[1] = 1, so low[0] stays 1.
25	L8	u=0 v=2	2 is already visited and younger: 2-0 is the same back edge seen from its upper end, and it was counted from 2. Min with tin[2] = 3 cannot lower low[0].
26	L15	u=0 tin=1 tout=10	0 is finished: tout[0] = 10. The interval [1, 10] contains the intervals of all of 0's descendants.
27	L15	return=1 tree_edges=4 back_edges=1	Done: 4 tree edges (n minus the number of DFS trees) and 1 back edge. Every non-tree edge of an undirected DFS joins an ancestor and a descendant.

38.01.5

Edge cases for multigraphs

A **multigraph** has parallel edges: two different roads between the same two towns. Low-link must treat them as two different edges, because two roads between u and v mean that losing one of them does not disconnect anything.

The tempting shortcut “skip the parent vertex” (if (v == parent) continue) throws away both roads at once, so u-v looks like a bridge. The fix is to remember the **edge id** you arrived by and skip only that id; the parallel copy then counts as an ordinary back edge to the parent and lowers low[v] to tin[parent].

Try the “Parallel edges” preset (0-1 0-1 1-2). Vertex 1 ends with low = 1 because the second copy of 0-1 is a back edge, so 0-1 is not a bridge, while 1-2 is. Self-loops never matter for connectivity, so this animation rejects them; in code they are harmless because a loop looks like a back edge to the vertex itself.

Java

1static class BridgeCount {
2    int timer = 0, bridges = 0;
3    int[] tin, low;
4    List<int[]>[] g;
5    boolean byVertex;                                   // true = the tempting bug: skip every edge to the parent vertex
6
7    @SuppressWarnings("unchecked")
8    BridgeCount(int n, int[][] edges, boolean byVertex) {
9        this.byVertex = byVertex;
10        tin = new int[n]; low = new int[n];
11        g = new List[n];
12        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
13        for (int k = 0; k < edges.length; k++) {
14            g[edges[k][0]].add(new int[]{edges[k][1], k});
15            g[edges[k][1]].add(new int[]{edges[k][0], k});
16        }
17    }
18
19    void dfs(int u, int parentVertex, int parentEdge) {
20        tin[u] = low[u] = ++timer;
21        for (int[] e : g[u]) {
22            int v = e[0], id = e[1];
23            if (byVertex ? v == parentVertex : id == parentEdge) continue;
24            if (tin[v] != 0) {
25                low[u] = Math.min(low[u], tin[v]);
26            } else {
27                dfs(v, u, id);
28                low[u] = Math.min(low[u], low[v]);
29                if (low[v] > tin[u]) bridges++;
30            }
31        }
32    }
33}
34
35static int countBridges(int n, int[][] edges, boolean byVertex) {
36    BridgeCount c = new BridgeCount(n, edges, byVertex);
37    for (int v = 0; v < n; v++) if (c.tin[v] == 0) c.dfs(v, -1, -1);
38    return c.bridges;
39}

DFS timestamps: tin, tout, low-link, tree and back edges

Interactive · edit the input

node caption: tin / tout · 5 vertices · 5 edges

Current vertex or edgeOpen vertex, or back edge (B)Finished vertex, or tree edge (T)

tin

–0

–1

–2

–3

–4

tout

–0

–1

–2

–3

–4

low

–0

–1

–2

–3

–4

Setup

Step 1 / 27

Java

1static int timer = 0;
2static int[] tin, tout, low;                          // tin 0 means "not visited yet"
3static void dfs(List<int[]>[] g, int u, int parentEdge) {   // g[u] holds {neighbour, edge id}
4    tin[u] = low[u] = ++timer;                        // entry time; low starts as its own entry time
5    for (int[] e : g[u]) {
6        int v = e[0], id = e[1];
7        if (id == parentEdge) continue;               // skip the edge we came by: by id, so a parallel copy still counts
8        if (tin[v] != 0) {                            // already visited
9            low[u] = Math.min(low[u], tin[v]);        // back edge to an ancestor (from an ancestor's side it changes nothing)
10        } else {
11            dfs(g, v, id);                            // tree edge: v is a new child
12            low[u] = Math.min(low[u], low[v]);        // whatever v's subtree reaches, u reaches
13        }
14    }
15    tout[u] = ++timer;                                // exit time: [tin, tout] nests like brackets
16}

Live state

0 tree edges0 back edges

edges

No condition evaluated on this step

Execution trace (dry run table)Show 27 steps

Step	Line	State	What happens
1	L1	n=5 edges=5	5 vertices and 5 edges. DFS starts at 0. It gives every vertex an entry time tin when first reached and an exit time tout when finished, and tracks low: the smallest entry time reachable from the subtree using tree edges downwards and at most one back edge.
2	L1	root=0	0 has not been visited, so start a new DFS tree here.
3	L4	u=0 tin=1 low=1	Enter 0: tin[0] = 1 and low[0] starts equal to it.
4	L11	u=0 v=1	1 is new: 0-1 becomes a tree edge and DFS goes down into 1.
5	L4	u=1 tin=2 low=2	Enter 1: tin[1] = 2 and low[1] starts equal to it.
6	L7	u=1 edge=0-1	Edge 0-1 is the one DFS used to reach 1; skip it by id. (A parallel copy of this edge would not be skipped.)
7	L11	u=1 v=2	2 is new: 1-2 becomes a tree edge and DFS goes down into 2.
8	L4	u=2 tin=3 low=3	Enter 2: tin[2] = 3 and low[2] starts equal to it.
9	L7	u=2 edge=1-2	Edge 1-2 is the one DFS used to reach 2; skip it by id. (A parallel copy of this edge would not be skipped.)
10	L9	u=2 v=0 tin_v=1 low=1	0 is visited and older (tin 1 < tin 3): 2-0 is a back edge up to an ancestor. low[2] drops from 3 to 1.
11	L11	u=2 v=3	3 is new: 2-3 becomes a tree edge and DFS goes down into 3.
12	L4	u=3 tin=4 low=4	Enter 3: tin[3] = 4 and low[3] starts equal to it.
13	L7	u=3 edge=2-3	Edge 2-3 is the one DFS used to reach 3; skip it by id. (A parallel copy of this edge would not be skipped.)
14	L11	u=3 v=4	4 is new: 3-4 becomes a tree edge and DFS goes down into 4.
15	L4	u=4 tin=5 low=5	Enter 4: tin[4] = 5 and low[4] starts equal to it.
16	L7	u=4 edge=3-4	Edge 3-4 is the one DFS used to reach 4; skip it by id. (A parallel copy of this edge would not be skipped.)
17	L15	u=4 tin=5 tout=6	4 is finished: tout[4] = 6. The interval [5, 6] contains the intervals of all of 4's descendants.
18	L12	u=3 v=4 low_v=5 low=4	Back at 3 from 4: low[4] = 5, so low[3] stays 4.
19	L15	u=3 tin=4 tout=7	3 is finished: tout[3] = 7. The interval [4, 7] contains the intervals of all of 3's descendants.
20	L12	u=2 v=3 low_v=4 low=1	Back at 2 from 3: low[3] = 4, so low[2] stays 1.
21	L15	u=2 tin=3 tout=8	2 is finished: tout[2] = 8. The interval [3, 8] contains the intervals of all of 2's descendants.
22	L12	u=1 v=2 low_v=1 low=1	Back at 1 from 2: low[2] = 1, so low[1] drops from 2 to 1.
23	L15	u=1 tin=2 tout=9	1 is finished: tout[1] = 9. The interval [2, 9] contains the intervals of all of 1's descendants.
24	L12	u=0 v=1 low_v=1 low=1	Back at 0 from 1: low[1] = 1, so low[0] stays 1.
25	L8	u=0 v=2	2 is already visited and younger: 2-0 is the same back edge seen from its upper end, and it was counted from 2. Min with tin[2] = 3 cannot lower low[0].
26	L15	u=0 tin=1 tout=10	0 is finished: tout[0] = 10. The interval [1, 10] contains the intervals of all of 0's descendants.
27	L15	return=1 tree_edges=4 back_edges=1	Done: 4 tree edges (n minus the number of DFS trees) and 1 back edge. Every non-tree edge of an undirected DFS joins an ancestor and a descendant.

Practice ladder

Now try it yourself

Easy

Find if Path Exists in Graph
Find Center of Star Graph

Medium

Number of Provinces
Number of Operations to Make Network Connected
Redundant Connection

Advanced

Critical Connections in a Network
Minimum Number of Days to Disconnect Island

Key takeaways

tin and tout nest like brackets; low[u] is the earliest entry time u's subtree can reach with one back edge.
In an undirected DFS every non-tree edge is a back edge between an ancestor and a descendant.
Skip the parent edge by id, never by vertex, so parallel edges are counted correctly.