graph

ソースコード

  1#include <vector>
  2#include <queue>
  3#include <stack>
  4#include <cassert>
  5#include <algorithm>
  6
  7#include "titan_cpplib/data_structures/union_find.cpp"
  8using namespace std;
  9
 10namespace titan23 {
 11
 12    class Graph {
 13      private:
 14        int n;
 15        vector<vector<int>> G;
 16        vector<pair<int, int>> E;
 17        static const int inf = 1e9;
 18
 19      public:
 20        Graph() : n(0), G(0) {}
 21
 22        Graph(int n) : n(n), G(n) {}
 23
 24        //! 辺(u, v)を追加する
 25        void add_edge(const int u, const int v) {
 26            assert(0 <= u && u < n);
 27            assert(0 <= v && v < n);
 28            G[u].emplace_back(v);
 29            E.emplace_back(u, v);
 30        }
 31
 32        vector<vector<int>> get_G() const {
 33            return G;
 34        }
 35
 36        vector<pair<int, int>> get_E() const {
 37            return E;
 38        }
 39
 40        bool is_bipartite() {
 41            vector<int> col(n, -1);
 42            for (int v = 0; v < n; ++v) {
 43                if (col[v] != -1) continue;
 44                col[v] = 0;
 45                queue<int> qu;
 46                qu.push(v);
 47                while (!qu.empty()) {
 48                    int v = qu.front();
 49                    qu.pop();
 50                    int cx = 1 - col[v];
 51                    for (const auto &x: G[v]) {
 52                        if (col[x] == -1) {
 53                            col[x] = cx;
 54                            qu.push(x);
 55                        } else if (col[x] != cx) {
 56                            return false;
 57                        }
 58                    }
 59                }
 60            }
 61            for (const int &c: col) {
 62                if (c == -1) {
 63                return false;
 64                }
 65            }
 66            return true;
 67        }
 68
 69        vector<int> bfs(const int start) {
 70            vector<int> dist(n, -1);
 71            queue<int> todo;
 72            todo.emplace(start);
 73            dist[start] = 0;
 74            while (!todo.empty()) {
 75                int v = todo.front(); todo.pop();
 76                for (const int &x : G[v]) {
 77                    if (dist[x] == -1) {
 78                        dist[x] = dist[v] + 1;
 79                        todo.emplace(x);
 80                    }
 81                }
 82            }
 83            return dist;
 84        }
 85
 86        vector<int> bfs_path(int s, int t) {
 87            vector<int> prev(n, -1);
 88            vector<int> dist(n, inf);
 89            dist[s] = 0;
 90            queue<int> todo;
 91            todo.emplace(s);
 92            while (!todo.empty()) {
 93                int v = todo.front();
 94                todo.pop();
 95                for (const int x : G[v]) {
 96                    if (dist[x] == inf) {
 97                        dist[x] = dist[v] + 1;
 98                        prev[x] = v;
 99                        todo.emplace(x);
100                    }
101                }
102            }
103            if (dist[t] == inf) {
104                return {};
105            }
106            vector<int> path;
107            while (prev[t] != -1) {
108                path.emplace_back(t);
109                t = prev[t];
110            }
111            path.emplace_back(t);
112            std::reverse(path.begin(), path.end());
113            return path;
114        }
115
116        int len() const {
117            return n;
118        }
119
120        vector<int> topological_sort() {
121            vector<int> d(n, 0);
122            for (int i = 0; i < n; ++i) {
123                for (const int &x: G[i]) {
124                    ++d[x];
125                }
126            }
127            vector<int> res;
128            stack<int> todo;
129            for (int i = 0; i < n; ++i) {
130                if (d[i] == 0) todo.emplace(i);
131            }
132            while (!todo.empty()) {
133                int v = todo.top(); todo.pop();
134                res.emplace_back(v);
135                for (const int &x: G[v]) {
136                    --d[x];
137                    if (d[x] == 0) {
138                        todo.emplace(x);
139                    }
140                }
141            }
142            return res;
143        }
144
145        vector<pair<int, int>> minimum_spanning_tree() {
146            titan23::UnionFind uf(n);
147            vector<pair<int, int>> ans;
148            for (const auto &[u, v] : E) {
149                if (uf.same(u, v)) continue;
150                uf.unite(u, v);
151                ans.emplace_back(u, v);
152            }
153            return ans;
154        }
155    };
156}  // namespace titan23

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/graph/graph.cpp