4.1.1 Adjacency Lists and DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161

/*

Stores a directed or undirected graph as adjacency lists. The list for node `u` contains its
out-neighbors; an undirected edge is stored in both endpoints' lists. Nodes are nonnegative integer
indices in $[0, `size()`)$, and `add_edge()` grows the graph when either endpoint is new. The class
also provides depth-first search, cycle detection, and forest/DAG checks.

Parallel edges and self-loops are stored as given, and the cycle checks read them as a multigraph
would: a self-loop is a cycle, and a repeated undirected edge is a cycle of length two. The
undirected search skips edges back to the parent by node index, so a duplicate is caught when the
parent scans it rather than when the child looks back.

- `Graph(directed = true)` constructs an empty graph, directed if `directed` is true and undirected
  otherwise.
- `size()` returns the current number of nodes.
- `operator[u]` returns a mutable or const reference to the adjacency list (`std::vector<int>`) of
  node `u`.
- `add_edge(u, v)` adds an edge from `u` to `v`, plus the reverse edge if the graph is undirected,
  growing the node count to accommodate the larger index if necessary.
- `dfs(start, f)` runs a depth-first search from node `start`, calling function `f` on each node in
  the order it is first visited.
- `has_cycle()` returns whether the graph contains a cycle.
- `is_directed()` returns whether the graph is directed.
- `is_forest()` returns whether the graph is undirected and acyclic.
- `is_dag()` returns whether the graph is directed and acyclic.

Time Complexity:
- O(1) amortized per call to `add_edge()` when no resize is required; up to O(n) for a call that
  grows the graph to $n$ nodes.
- O(max(n, m)) per call for `dfs()`, `has_cycle()`, `is_forest()`, or `is_dag()`, where $n$ is the
  number of nodes and $m$ is the number of edges.
- O(1) per call to all other public member functions.

Space Complexity:
- O(max(n, m)) for storage of the graph, where $n$ is the number of nodes and $m$ is the number of
  edges.
- O(n) auxiliary stack space for `dfs()`, `has_cycle()`, `is_forest()`, and `is_dag()`.
- O(1) auxiliary for all other public member functions.

*/

#include <algorithm>
#include <vector>

class Graph {
  std::vector<std::vector<int>> adj;
  bool directed;

 public:
  explicit Graph(bool directed = true) : directed(directed) {}

  int size() const { return static_cast<int>(adj.size()); }
  std::vector<int> &operator[](int u) { return adj[u]; }
  const std::vector<int> &operator[](int u) const { return adj[u]; }

  void add_edge(int u, int v) {
    int n = static_cast<int>(adj.size());
    if (u >= n || v >= n) {
      adj.resize(std::max(u, v) + 1);
    }
    adj[u].push_back(v);
    if (!directed) {
      adj[v].push_back(u);
    }
  }

  template<typename Fn>
  void dfs(int start, Fn f) const {
    std::vector<char> visit(adj.size());
    auto dfs = [&](auto &&dfs, int u) -> void {
      f(u);
      visit[u] = true;
      for (int v : adj[u]) {
        if (!visit[v]) {
          dfs(dfs, v);
        }
      }
    };
    dfs(dfs, start);
  }

  bool has_cycle() const {
    int n = static_cast<int>(adj.size());
    std::vector<char> visit(n), onstack(n);
    auto dfs = [&](auto &&dfs, int u, int p) -> bool {
      visit[u] = true;
      onstack[u] = true;
      for (int v : adj[u]) {
        if ((directed && onstack[v]) ||           // back edge in directed graph
            (!directed && visit[v] && v != p) ||  // back edge in undirected graph
            (!visit[v] && dfs(dfs, v, u))) {      // tree edge to unvisited node
          return true;
        }
      }
      onstack[u] = false;
      return false;
    };
    for (int i = 0; i < n; i++) {
      if (!visit[i] && dfs(dfs, i, -1)) {
        return true;
      }
    }
    return false;
  }

  bool is_directed() const { return directed; }
  bool is_forest() const { return !directed && !has_cycle(); }
  bool is_dag() const { return directed && !has_cycle(); }
};

/*** Example Usage ***/

#include <cassert>
using namespace std;

int main() {
  //           0
  //       /  /  |
  //      v  v   v
  //      1  6   7
  //    / |     / |
  //   v  v    v  v
  //   2  5    8  11
  //  / |     /|
  // v  v    v v
  // 3  4    9 10
  Graph g;
  g.add_edge(0, 1);
  g.add_edge(0, 6);
  g.add_edge(0, 7);
  g.add_edge(1, 2);
  g.add_edge(1, 5);
  g.add_edge(2, 3);
  g.add_edge(2, 4);
  g.add_edge(7, 8);
  g.add_edge(7, 11);
  g.add_edge(8, 9);
  g.add_edge(8, 10);
  vector<int> order;
  g.dfs(0, [&](int u) { order.push_back(u); });
  assert((order == vector<int>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}));
  assert(g.size() == 12 && g[0].size() == 3);
  assert(g.is_dag());
  assert(!g.has_cycle());

  //       0
  //     /  |
  //    1   2
  //  / |
  // 3  4
  Graph tree(false);
  tree.add_edge(0, 1);
  tree.add_edge(0, 2);
  tree.add_edge(1, 3);
  tree.add_edge(1, 4);
  assert(tree.is_forest());
  assert(!tree.is_dag());
  tree.add_edge(2, 3);
  assert(!tree.is_forest());
  return 0;
}