32.04Intermediate / Advanced6 topics14 min6 interactive animations

Graph construction

Turning raw input into a graph without surprises: indexing, duplicate edges, self-loops, weights, disconnected graphs and reversing edges.

Learning goals

Convert 1-based input to 0-based vertices at the boundary
Decide what to do with duplicate edges and self-loops
Store weights safely and represent 'no edge'
Handle disconnected graphs and build the reverse of a directed graph

Prerequisites

Representations

Most graph bugs are not in the algorithm but in the input: a vertex numbered from 1, a repeated edge counted twice, a loop that sends a search around in circles, a vertex nobody connected. Build the graph carefully once and the rest is easier.

32.04.1

0-based/1-based indexing

Problem statements usually number vertices 1..n; arrays start at 0. Either allocate n + 1 slots and ignore index 0, or subtract 1 from every input vertex as the graph is built. The second is cleaner inside the algorithm, but you must add 1 again when printing. Pick one convention for the whole program and convert only at the input and output boundaries.

Mixing the two is the classic off-by-one bug: an edge 1-3 stored as [1][3] in a 3-slot array crashes, or silently shifts every answer. The code below builds 0-based neighbour lists from 1-based or 0-based edges with a flag.

Java

1static List<List<Integer>> build(int n, int[][] edges, boolean oneBased, boolean directed) {
2    int shift = oneBased ? 1 : 0;
3    List<List<Integer>> g = new ArrayList<>();
4    for (int i = 0; i < n; i++) g.add(new ArrayList<>());
5    for (int[] e : edges) {
6        int a = e[0] - shift, b = e[1] - shift;          // convert once, here
7        g.get(a).add(b);
8        if (!directed) g.get(b).add(a);
9    }
10    return g;
11}

One graph, three representations: matrix, adjacency list, edge list

Interactive · edit the input

grid · 6 × 6

012345

Just addedChanged entryHeader

undirected graph · 5 vertices · 0 edges

Just addedChanged entryHeader

list[0]

empty

list[1]

empty

list[2]

empty

list[3]

empty

list[4]

empty

edge list (a-b, weight)

empty

Setup

An empty undirected graph on 5 vertices. The three representations below are always updated together: the matrix always has 5 × 5 = 25 cells, the adjacency list grows with the edges, and the edge list is just the edges.

Step 1 / 7

Java

1int[][] matrix = new int[n][n];                  // adjacency matrix: n * n cells
2List<List<int[]>> list = new ArrayList<>();      // adjacency list: {neighbour, weight} per vertex
3for (int i = 0; i < n; i++) list.add(new ArrayList<>());
4int[][] edgeList = new int[m][];                 // edge list: {a, b, weight}
5void addEdge(int k, int a, int b, int w, boolean directed) {
6    edgeList[k] = new int[]{a, b, w};
7    matrix[a][b]++;                              // directed: this one cell is the whole edge
8    list.get(a).add(new int[]{b, w});
9    if (!directed) {
10        matrix[b][a]++;                          // undirected: also the mirror cell (a self-loop counts twice on the diagonal)
11        list.get(b).add(new int[]{a, w});
12    }
13}

Live state

0 edges added0 list entries

edges

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L1	n=5 edges=5	An empty undirected graph on 5 vertices. The three representations below are always updated together: the matrix always has 5 × 5 = 25 cells, the adjacency list grows with the edges, and the edge list is just the edges.
2	L10	edge=0-1 matrix cells changed=2 list entries=2	Add the edge 0-1: both mirror cells [0][1] and [1][0], two list entries and one edge-list entry.
3	L10	edge=0-2 matrix cells changed=2 list entries=4	Add the edge 0-2: both mirror cells [0][2] and [2][0], two list entries and one edge-list entry.
4	L10	edge=1-3 matrix cells changed=2 list entries=6	Add the edge 1-3: both mirror cells [1][3] and [3][1], two list entries and one edge-list entry.
5	L10	edge=2-3 matrix cells changed=2 list entries=8	Add the edge 2-3: both mirror cells [2][3] and [3][2], two list entries and one edge-list entry.
6	L10	edge=3-4 matrix cells changed=2 list entries=10	Add the edge 3-4: both mirror cells [3][4] and [4][3], two list entries and one edge-list entry.
7	L13	return=[2, 2, 2, 3, 1] sum of degrees=10 edges=5	Degrees (row sums) [2, 2, 2, 3, 1]; they add up to 10 = 2 × 5: every edge has two ends (handshaking lemma).

32.04.2

Duplicate edges

The same pair may appear twice in the input. For counting problems a repeat is a real second edge (a multigraph); for shortest paths a repeat is harmless but only the lighter one matters; for a simple-graph theorem you must remove it. An adjacency matrix with 0/1 entries silently merges duplicates, a list keeps them. Decide deliberately and say so in a comment.

The preset "Duplicate edge and self-loop" adds 0-1 twice: the matrix cell becomes 2 and vertex 0's list has two entries. The code below merges duplicates in an undirected weighted graph, keeping the smallest weight for each pair.

Java

1static int[][] dedupe(int[][] edges) {           // undirected {a, b, w}: one edge per pair, the lightest
2    Map<Long, int[]> best = new TreeMap<>();
3    for (int[] e : edges) {
4        int a = Math.min(e[0], e[1]), b = Math.max(e[0], e[1]);   // {a, b} and {b, a} are the same pair
5        long key = (long) a * 1_000_000 + b;
6        int[] cur = best.get(key);
7        if (cur == null || e[2] < cur[2]) best.put(key, new int[]{a, b, e[2]});
8    }
9    return best.values().toArray(new int[0][]);
10}

One graph, three representations: matrix, adjacency list, edge list

Interactive · edit the input

grid · 6 × 6

012345

Just addedChanged entryHeader

undirected graph · 5 vertices · 0 edges

Just addedChanged entryHeader

list[0]

empty

list[1]

empty

list[2]

empty

list[3]

empty

list[4]

empty

edge list (a-b, weight)

empty

Setup

Step 1 / 7

Java

1int[][] matrix = new int[n][n];                  // adjacency matrix: n * n cells
2List<List<int[]>> list = new ArrayList<>();      // adjacency list: {neighbour, weight} per vertex
3for (int i = 0; i < n; i++) list.add(new ArrayList<>());
4int[][] edgeList = new int[m][];                 // edge list: {a, b, weight}
5void addEdge(int k, int a, int b, int w, boolean directed) {
6    edgeList[k] = new int[]{a, b, w};
7    matrix[a][b]++;                              // directed: this one cell is the whole edge
8    list.get(a).add(new int[]{b, w});
9    if (!directed) {
10        matrix[b][a]++;                          // undirected: also the mirror cell (a self-loop counts twice on the diagonal)
11        list.get(b).add(new int[]{a, w});
12    }
13}

Live state

0 edges added0 list entries

edges

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L1	n=5 edges=5	An empty undirected graph on 5 vertices. The three representations below are always updated together: the matrix always has 5 × 5 = 25 cells, the adjacency list grows with the edges, and the edge list is just the edges.
2	L10	edge=0-1 matrix cells changed=2 list entries=2	Add the edge 0-1: both mirror cells [0][1] and [1][0], two list entries and one edge-list entry.
3	L10	edge=0-2 matrix cells changed=2 list entries=4	Add the edge 0-2: both mirror cells [0][2] and [2][0], two list entries and one edge-list entry.
4	L10	edge=1-3 matrix cells changed=2 list entries=6	Add the edge 1-3: both mirror cells [1][3] and [3][1], two list entries and one edge-list entry.
5	L10	edge=2-3 matrix cells changed=2 list entries=8	Add the edge 2-3: both mirror cells [2][3] and [3][2], two list entries and one edge-list entry.
6	L10	edge=3-4 matrix cells changed=2 list entries=10	Add the edge 3-4: both mirror cells [3][4] and [4][3], two list entries and one edge-list entry.
7	L13	return=[2, 2, 2, 3, 1] sum of degrees=10 edges=5	Degrees (row sums) [2, 2, 2, 3, 1]; they add up to 10 = 2 × 5: every edge has two ends (handshaking lemma).

32.04.3

Self-loops

A **self-loop** joins a vertex to itself. In an undirected graph it adds 2 to the degree; in a traversal it must not make a search follow it forever (a visited array prevents that). For many problems a loop is meaningless: it never helps a shortest path (with non-negative weights) and never joins two components. Drop loops when the problem allows, count them when it does not.

In the preset "Duplicate edge and self-loop" the edge 1-1 adds 2 to the diagonal cell and to vertex 1's degree, which is why vertex 1 has degree 5 (0-1, 0-1, 1-1 counted twice, 1-2). The code removes loops and counts them.

Java

1static int countSelfLoops(int[][] edges) {
2    int count = 0;
3    for (int[] e : edges) if (e[0] == e[1]) count++;
4    return count;
5}
6static int[][] withoutSelfLoops(int[][] edges) {
7    return Arrays.stream(edges).filter(e -> e[0] != e[1]).toArray(int[][]::new);
8}

One graph, three representations: matrix, adjacency list, edge list

Interactive · edit the input

grid · 6 × 6

012345

Just addedChanged entryHeader

undirected graph · 5 vertices · 0 edges

Just addedChanged entryHeader

list[0]

empty

list[1]

empty

list[2]

empty

list[3]

empty

list[4]

empty

edge list (a-b, weight)

empty

Setup

Step 1 / 7

Java

1int[][] matrix = new int[n][n];                  // adjacency matrix: n * n cells
2List<List<int[]>> list = new ArrayList<>();      // adjacency list: {neighbour, weight} per vertex
3for (int i = 0; i < n; i++) list.add(new ArrayList<>());
4int[][] edgeList = new int[m][];                 // edge list: {a, b, weight}
5void addEdge(int k, int a, int b, int w, boolean directed) {
6    edgeList[k] = new int[]{a, b, w};
7    matrix[a][b]++;                              // directed: this one cell is the whole edge
8    list.get(a).add(new int[]{b, w});
9    if (!directed) {
10        matrix[b][a]++;                          // undirected: also the mirror cell (a self-loop counts twice on the diagonal)
11        list.get(b).add(new int[]{a, w});
12    }
13}

Live state

0 edges added0 list entries

edges

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L1	n=5 edges=5	An empty undirected graph on 5 vertices. The three representations below are always updated together: the matrix always has 5 × 5 = 25 cells, the adjacency list grows with the edges, and the edge list is just the edges.
2	L10	edge=0-1 matrix cells changed=2 list entries=2	Add the edge 0-1: both mirror cells [0][1] and [1][0], two list entries and one edge-list entry.
3	L10	edge=0-2 matrix cells changed=2 list entries=4	Add the edge 0-2: both mirror cells [0][2] and [2][0], two list entries and one edge-list entry.
4	L10	edge=1-3 matrix cells changed=2 list entries=6	Add the edge 1-3: both mirror cells [1][3] and [3][1], two list entries and one edge-list entry.
5	L10	edge=2-3 matrix cells changed=2 list entries=8	Add the edge 2-3: both mirror cells [2][3] and [3][2], two list entries and one edge-list entry.
6	L10	edge=3-4 matrix cells changed=2 list entries=10	Add the edge 3-4: both mirror cells [3][4] and [4][3], two list entries and one edge-list entry.
7	L13	return=[2, 2, 2, 3, 1] sum of degrees=10 edges=5	Degrees (row sums) [2, 2, 2, 3, 1]; they add up to 10 = 2 × 5: every edge has two ends (handshaking lemma).

32.04.4

Weights

Weights belong to edges, so store them beside the neighbour: {v, w} pairs in a list, a weight matrix, or a parallel array in CSR. Use long for sums of weights, since a path of many edges can overflow int. For 'no edge' in a weight matrix use a large sentinel, not Integer.MAX_VALUE, because adding two sentinels overflows; Long.MAX_VALUE / 4 is safe to add a few times.

The preset "Weights" (0-1:4 0-2:1 1-2:2 2-3:7) shows each list entry as neighbour:weight. The code builds a weight matrix with a safe 'infinity' and keeps the lightest of parallel edges.

Java

1static final long INF = Long.MAX_VALUE / 4;      // adding two of these cannot overflow
2static long[][] weightMatrix(int n, int[][] edges) {          // undirected {a, b, w}
3    long[][] w = new long[n][n];
4    for (long[] row : w) Arrays.fill(row, INF);
5    for (int i = 0; i < n; i++) w[i][i] = 0;
6    for (int[] e : edges) {
7        w[e[0]][e[1]] = Math.min(w[e[0]][e[1]], e[2]);       // parallel edges: keep the lightest
8        w[e[1]][e[0]] = Math.min(w[e[1]][e[0]], e[2]);
9    }
10    return w;
11}

One graph, three representations: matrix, adjacency list, edge list

Interactive · edit the input

grid · 6 × 6

012345

Just addedChanged entryHeader

undirected graph · 5 vertices · 0 edges

Just addedChanged entryHeader

list[0]

empty

list[1]

empty

list[2]

empty

list[3]

empty

list[4]

empty

edge list (a-b, weight)

empty

Setup

Step 1 / 7

Java

1int[][] matrix = new int[n][n];                  // adjacency matrix: n * n cells
2List<List<int[]>> list = new ArrayList<>();      // adjacency list: {neighbour, weight} per vertex
3for (int i = 0; i < n; i++) list.add(new ArrayList<>());
4int[][] edgeList = new int[m][];                 // edge list: {a, b, weight}
5void addEdge(int k, int a, int b, int w, boolean directed) {
6    edgeList[k] = new int[]{a, b, w};
7    matrix[a][b]++;                              // directed: this one cell is the whole edge
8    list.get(a).add(new int[]{b, w});
9    if (!directed) {
10        matrix[b][a]++;                          // undirected: also the mirror cell (a self-loop counts twice on the diagonal)
11        list.get(b).add(new int[]{a, w});
12    }
13}

Live state

0 edges added0 list entries

edges

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L1	n=5 edges=5	An empty undirected graph on 5 vertices. The three representations below are always updated together: the matrix always has 5 × 5 = 25 cells, the adjacency list grows with the edges, and the edge list is just the edges.
2	L10	edge=0-1 matrix cells changed=2 list entries=2	Add the edge 0-1: both mirror cells [0][1] and [1][0], two list entries and one edge-list entry.
3	L10	edge=0-2 matrix cells changed=2 list entries=4	Add the edge 0-2: both mirror cells [0][2] and [2][0], two list entries and one edge-list entry.
4	L10	edge=1-3 matrix cells changed=2 list entries=6	Add the edge 1-3: both mirror cells [1][3] and [3][1], two list entries and one edge-list entry.
5	L10	edge=2-3 matrix cells changed=2 list entries=8	Add the edge 2-3: both mirror cells [2][3] and [3][2], two list entries and one edge-list entry.
6	L10	edge=3-4 matrix cells changed=2 list entries=10	Add the edge 3-4: both mirror cells [3][4] and [4][3], two list entries and one edge-list entry.
7	L13	return=[2, 2, 2, 3, 1] sum of degrees=10 edges=5	Degrees (row sums) [2, 2, 2, 3, 1]; they add up to 10 = 2 × 5: every edge has two ends (handshaking lemma).

32.04.5

Disconnected graphs

Never assume a graph is connected. A search from vertex 0 reaches only vertex 0's component; to cover the whole graph, loop over all vertices and start a new search from every unvisited one. The same loop counts the components, and the unreached vertices are exactly the 'unreachable' answers.

The preset "Three components" in the components animation starts a new search each time the outer loop finds an unlabelled vertex. The code returns one starting vertex per component: the smallest vertex of each.

Java

1static List<Integer> componentStarts(List<List<Integer>> g) {      // the smallest vertex of every component
2    int n = g.size();
3    boolean[] seen = new boolean[n];
4    List<Integer> starts = new ArrayList<>();
5    for (int s = 0; s < n; s++) {
6        if (seen[s]) continue;
7        starts.add(s);                           // a new component begins here
8        Deque<Integer> stack = new ArrayDeque<>();
9        stack.push(s); seen[s] = true;
10        while (!stack.isEmpty()) {
11            int u = stack.pop();
12            for (int v : g.get(u)) if (!seen[v]) { seen[v] = true; stack.push(v); }
13        }
14    }
15    return starts;
16}

Components, two-colouring and cycle detection in an undirected graph

Interactive · edit the input

undirected graph · 8 vertices · 6 edges

Colour / component AColour / component BComponent CConflictBeing expanded

component of each vertex

-0

-1

-2

-3

-4

-5

-6

-7

Setup

Search from an unlabelled vertex: everything the search reaches is one component. Repeat from the next unlabelled vertex until every vertex has a label.

Step 1 / 13

Java

1int[] components(List<List<Integer>> g) {        // component id per vertex
2    int n = g.size(); int[] comp = new int[n]; Arrays.fill(comp, -1);
3    int id = 0;
4    for (int s = 0; s < n; s++) {
5        if (comp[s] != -1) continue;
6        Deque<Integer> q = new ArrayDeque<>(); q.add(s); comp[s] = id;
7        while (!q.isEmpty()) {
8            int u = q.poll();
9            for (int v : g.get(u)) if (comp[v] == -1) { comp[v] = id; q.add(v); }
10        }
11        id++;                                    // the search ended: one whole component labelled
12    }
13    return comp;
14}
15boolean isBipartite(List<List<Integer>> g) {
16    int n = g.size(); int[] color = new int[n]; Arrays.fill(color, -1);
17    for (int s = 0; s < n; s++) {                // check every component
18        if (color[s] != -1) continue;
19        color[s] = 0; Deque<Integer> q = new ArrayDeque<>(); q.add(s);
20        while (!q.isEmpty()) {
21            int u = q.poll();
22            for (int v : g.get(u)) {
23                if (color[v] == -1) { color[v] = color[u] ^ 1; q.add(v); }
24                else if (color[v] == color[u]) return false;        // an odd cycle
25            }
26        }
27    }
28    return true;
29}
30boolean hasCycle(int n, List<int[]>[] g) {       // undirected; g[u] holds {v, edgeId}
31    boolean[] seen = new boolean[n];
32    for (int s = 0; s < n; s++) if (!seen[s] && dfsCycle(g, s, -1, seen)) return true;
33    return false;
34}
35boolean dfsCycle(List<int[]>[] g, int u, int viaEdge, boolean[] seen) {
36    seen[u] = true;
37    for (int[] e : g[u]) {
38        if (e[1] == viaEdge) continue;           // do not walk back along the edge we came by
39        if (seen[e[0]] || dfsCycle(g, e[0], e[1], seen)) return true;   // a seen vertex reached by another edge: a cycle
40    }
41    return false;
42}

Live state

0 components0 vertices visited

vertices

edges

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L2	vertices=8 edges=6	Search from an unlabelled vertex: everything the search reaches is one component. Repeat from the next unlabelled vertex until every vertex has a label.
2	L6	start=0 component=0	Vertex 0 is unlabelled: start component C1 here.
3	L9	u=0 v=1 component=0	0 - 1: 1 is unlabelled, so it belongs to C1 too.
4	L9	u=1 v=2 component=0	1 - 2: 2 is unlabelled, so it belongs to C1 too.
5	L11	components=1	The queue is empty: component C1 is complete. 1 so far.
6	L6	start=3 component=1	Vertex 3 is unlabelled: start component C2 here.
7	L9	u=3 v=4 component=1	3 - 4: 4 is unlabelled, so it belongs to C2 too.
8	L11	components=2	The queue is empty: component C2 is complete. 2 so far.
9	L6	start=5 component=2	Vertex 5 is unlabelled: start component C3 here.
10	L9	u=5 v=6 component=2	5 - 6: 6 is unlabelled, so it belongs to C3 too.
11	L9	u=5 v=7 component=2	5 - 7: 7 is unlabelled, so it belongs to C3 too.
12	L11	components=3	The queue is empty: component C3 is complete. 3 so far.
13	L13	return=3 sizes=[3, 2, 3]	3 components with sizes [3, 2, 3]. A vertex with no edge is a component of size 1. Cost O(V + E).

32.04.6

Reversing edges

The **reverse** (transpose) of a directed graph flips every arrow u → v into v → u. It costs O(V + E) and makes 'who can reach me?' as easy as 'whom can I reach?': a search in the reverse graph from t finds all vertices that can reach t. It is also the key step of Kosaraju's algorithm for strongly connected components. Out-degrees and in-degrees swap.

In the animation's "Reverse a directed graph" preset, edges 0-1 0-2 1-3 2-3 3-4 flip one by one and the final message shows the out-degrees [0, 1, 1, 2, 1] and in-degrees [2, 1, 1, 1, 0], the original in- and out-degrees swapped.

Java

1static List<List<Integer>> reverse(List<List<Integer>> g) {        // directed: flip every edge
2    List<List<Integer>> r = new ArrayList<>();
3    for (int i = 0; i < g.size(); i++) r.add(new ArrayList<>());
4    for (int u = 0; u < g.size(); u++)
5        for (int v : g.get(u)) r.get(v).add(u);              // u -> v becomes v -> u
6    return r;
7}

Graph complement, edge reversal and the tree test

Interactive · edit the input

undirected graph · 5 vertices · 4 edges

New edgeOriginal edgeBeing examinedNot a tree edge

Setup

The complement has the same vertices and exactly the pairs that are NOT edges. A simple graph on 5 vertices has n(n-1)/2 = 10 possible edges; 4 are present, so the complement will have 6.

Step 1 / 12

Java

1boolean[][] complement(boolean[][] adj) {        // simple undirected graph
2    int n = adj.length;
3    boolean[][] c = new boolean[n][n];
4    for (int i = 0; i < n; i++)
5        for (int j = 0; j < n; j++)
6            if (i != j) c[i][j] = !adj[i][j];    // an edge is present exactly when it was absent
7    return c;
8}
9List<List<Integer>> reverse(List<List<Integer>> g) {     // directed: flip every edge
10    List<List<Integer>> r = new ArrayList<>();
11    for (int i = 0; i < g.size(); i++) r.add(new ArrayList<>());
12    for (int u = 0; u < g.size(); u++)
13        for (int v : g.get(u)) r.get(v).add(u);          // u -> v becomes v -> u
14    return r;
15}
16boolean isTree(int n, int[][] edges) {           // n - 1 edges and connected (no cycle then follows)
17    if (edges.length != n - 1) return false;
18    DSU d = new DSU(n);
19    for (int[] e : edges) if (!d.union(e[0], e[1])) return false;    // an edge inside one set would close a cycle
20    return true;
21}

Live state

0 edges

edges

possible edges

No condition evaluated on this step

Execution trace (dry run table)Show 12 steps

Step	Line	State	What happens
1	L1	edges=4 possible edges=10	The complement has the same vertices and exactly the pairs that are NOT edges. A simple graph on 5 vertices has n(n-1)/2 = 10 possible edges; 4 are present, so the complement will have 6.
2	L6	pair=0-1 present=true complement edges=0	0-1 is an edge of the graph, so it is missing from the complement.
3	L6	pair=0-2 present=false complement edges=1	0-2 is not an edge, so it becomes an edge of the complement.
4	L6	pair=0-3 present=false complement edges=2	0-3 is not an edge, so it becomes an edge of the complement.
5	L6	pair=0-4 present=false complement edges=3	0-4 is not an edge, so it becomes an edge of the complement.
6	L6	pair=1-2 present=true complement edges=3	1-2 is an edge of the graph, so it is missing from the complement.
7	L6	pair=1-3 present=false complement edges=4	1-3 is not an edge, so it becomes an edge of the complement.
8	L6	pair=1-4 present=false complement edges=5	1-4 is not an edge, so it becomes an edge of the complement.
9	L6	pair=2-3 present=true complement edges=5	2-3 is an edge of the graph, so it is missing from the complement.
10	L6	pair=2-4 present=false complement edges=6	2-4 is not an edge, so it becomes an edge of the complement.
11	L6	pair=3-4 present=true complement edges=6	3-4 is an edge of the graph, so it is missing from the complement.
12	L7	return=6 graph + complement=10	The complement has 6 edges, and 4 + 6 = 10: together they make the complete graph.

Practice ladder

Now try it yourself

Easy

Find the Town Judge
Find Center of Star Graph

Medium

Clone Graph
Number of Operations to Make Network Connected

Advanced

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

Key takeaways

Convert 1-based input to 0-based once, at the boundary.
Decide on duplicates and self-loops explicitly; use long sums and a safe infinity for weights.
Loop over all vertices for disconnected graphs; reversing a directed graph is O(V + E).