@@ -0,0 +1,2 @@
+template <class E>
+using Graph = vector<vector<E>>;
@@ -0,0 +1,24 @@
+/**
+ * 橋の検出
+ */
+struct Bridge {
+    int gc;
+    vector<int> ig; // i to group
+    vector<int> gpar; // group par
+
+    template<class E>
+    void exec(const Graph<E> &g, int r) {
+        int V = (int)g.size();
+        LowLink lc(g, r);
+        ig.resize(V);
+        gc = 0;
+        for (int p: lc.vlis) {
+            if (lc.low[p] == lc.ord[p]) {
+                ig[p] = gc++;
+                gpar.push_back((p == r) ? -1 : ig[lc.par[p]]);
+            } else {
+                ig[p] = ig[lc.par[p]];
+            }
+        }
+    }
+};
@@ -0,0 +1,35 @@
+/**
+ * Dijkstra法により最短距離を求める
+ *
+ * template引数のint Vは頂点数
+ * ---
+ * struct Edge {
+ *     int to;
+ *     T dist;
+ * };
+ * ---
+ */
+template<class D, D INF>
+struct Dijkstra {
+    vector<D> res; //res[i] = sからiまでの最短距離
+    
+    template<class E>
+    void exec(const Graph<E> &g, int s) {
+        int V = (int)g.size();
+        res.resize(V); fill_n(res.begin(), V, INF);
+        using P = pair<D, int>;
+        priority_queue<P, vector<P>, greater<P>> q;
+        q.push(P(0, s));
+        res[s] = 0;
+        while (!q.empty()) {
+            P p = q.top(); q.pop();
+            if (res[p.second] < p.first) continue;
+            for (E e: g[p.second]) {
+                if (p.first+e.dist < res[e.to]) {
+                    res[e.to] = p.first+e.dist;
+                    q.push(P(res[e.to], e.to));
+                }
+            }
+        }
+    }
+};
@@ -0,0 +1,63 @@
+/**
+ * Dominator Tree
+ */
+struct Dominator {
+    vector<int> idom, sdom;
+
+    LowLink lc;
+
+    Dominator() {}
+    template<class E>
+    Dominator(const Graph<E> &g, const Graph<E> &rg, int s) {
+        exec(g, rg, s);
+    }
+
+    template<class E>
+    void exec(const Graph<E> &g, const Graph<E> &rg, int s) {
+        int V = (int)g.size();
+
+        lc = LowLink(g, 0);
+        
+        // uf init
+        p.resize(V); mv.resize(V);
+        fill_n(p.begin(), V, -1);
+        iota(mv.begin(), mv.end(), 0);
+        idom.resize(V); sdom.resize(V);
+        iota(sdom.begin(), sdom.end(), 0);
+
+        vector<int> up(V);
+        vector<vector<int>> bucket(V);
+        for (int i = V-1; i > 0; i--) {
+            int u = lc.vlis[i];
+            for (E e: rg[u]) {
+                sdom[u] = lc.vlis[min(lc.ord[sdom[u]], lc.ord[sdom[compress(e.to)]])];
+            }
+            bucket[sdom[u]].push_back(u);
+            for (int v: bucket[lc.par[u]]) {
+                up[v] = compress(v);
+            }
+            bucket[lc.par[u]].clear();
+            p[u] = lc.par[u]; // uf merge
+        }
+
+        idom[s] = -1;
+        for (int i = 1; i < V; i++) {
+            int u = lc.vlis[i], v = up[u];
+            if (sdom[u] == sdom[v]) idom[u] = sdom[u];
+            else idom[u] = idom[v];
+        }
+    }
+
+    // unionfind
+    vector<int> p, mv; // parent, min sdom's v
+    int compress(int a) {
+        if (p[a] != -1) {
+            compress(p[a]);
+            if (lc.ord[sdom[mv[a]]] > lc.ord[sdom[mv[p[a]]]]) {
+                mv[a] = mv[p[a]];
+            }
+            p[a] = (p[p[a]] == -1 ? p[a] : p[p[a]]);
+        }
+        return mv[a];
+    }
+};
@@ -0,0 +1,50 @@
+/**
+ * LCA(lowest common ancestor)
+ */
+template<int LG = 20>
+struct LCA {
+    vector<int> ro[LG], dps;
+
+    /// 事前処理を行う rはroot頂点のid
+    template<class E>
+    void exec(const Graph<E> &g, int r) {
+        int V = (int)g.size();
+        for (int i = 0; i < LG; i++) {
+            ro[i].resize(V);
+            fill_n(ro[i].begin(), V, -1);
+        }
+        dps.resize(V);
+        dfs(g, r, -1, 0);
+        for (int i = 1; i < LG; i++) {
+            for (int j = 0; j < V; j++) {
+                ro[i][j] = (ro[i-1][j] == -1) ? -1 : ro[i-1][ro[i-1][j]];
+            }
+        }
+    }
+    /// lとrの頂点のLCAを求める
+    int query(int l, int r) {
+        if (dps[l] < dps[r]) swap(l, r);
+        int dd = dps[l]-dps[r];
+        for (int i = LG-1; i >= 0; i--) {
+            if (dd < (1<<i)) continue;
+            dd -= 1<<i;
+            l = ro[i][l];
+        }
+        if (l == r) return l;
+        for (int i = LG-1; i >= 0; i--) {
+            if (ro[i][l] == ro[i][r]) continue;
+            l = ro[i][l]; r = ro[i][r];
+        }
+        return ro[0][l];
+    }
+    
+    template<class E>
+    void dfs(const Graph<E> &g, int p, int b, int now) {
+        ro[0][p] = b;
+        dps[p] = now;
+        for (E e: g[p]) {
+            if (e.to == b) continue;
+            dfs(g, e.to, p, now+1);
+        }
+    }
+};
@@ -0,0 +1,50 @@
+/**
+ * LowLink
+ * dfs木についてのいろいろな情報を求める
+ */
+struct LowLink {
+    vector<int> low, ord, par;
+    vector<int> vlis;
+    
+    LowLink() {}
+    template<class E>
+    LowLink(const Graph<E> &g, int r) { exec(g, r); }
+
+    template<class E>
+    void exec(const Graph<E> &g, int r) {
+        int V = (int)g.size();
+        low.resize(V); ord.resize(V); par.resize(V);
+        co = 0; used.resize(V);
+        fill_n(used.begin(), V, false);
+        if (r != -1) {
+            dfs(g, r, -1);
+        } else {
+            for (int i = 0; i < n; i++) {
+                if (used[i]) continue;
+                dfs(g, i, -1);
+            }
+        }
+    }
+    int co;
+    vector<bool> used;
+    template<class E>
+    void dfs(const Graph<E> &g, int p, int b) {
+        used[p] = true;
+        bool rt = true;
+        low[p] = ord[p] = co++;
+        vlis.push_back(p);
+        par[p] = b;
+        for (E e: g[p]) {
+            if (rt and e.to == b) {
+                rt = false;
+                continue;
+            }
+            if (!used[e.to]) {
+                dfs(g, e.to, p);
+                low[p] = min(low[p], low[e.to]);
+            } else {
+                low[p] = min(low[p], ord[e.to]);
+            }
+        }
+    }
+};
@@ -0,0 +1,74 @@
+/**
+ * Dinic法による最大流
+ *
+ * ほとんど蟻本そのまま
+ * template引数のint Vは頂点数
+ * Edgeにはrevが必要
+ * ---
+ * void add_edge(Graph<Edge> &g, int from, int to, int cap) {
+ *     g[from].push_back(Edge{to, cap, (int)g[to].size()});
+ *     g[to].push_back(Edge{from, 0, (int)g[from].size()-1});
+ * }
+ * ---
+ */
+template<class T> // Tは容量の型
+struct MaxFlow {
+    const T INF = TEN(9);
+
+    int V;
+    vector<int> level, iter;
+
+    //gを破壊するので注意
+    template<class E>
+    T exec(Graph<E> &g, int s, int t) {
+        V = (int)g.size();
+        level.resize(V);
+        iter.resize(V);
+        T flow = 0;
+        while (true) {
+            bfs(g, s);
+            if (level[t] < 0) return flow;
+            fill_n(iter.begin(), V, 0);
+            while (true) {
+                T f = dfs(g, s, t, INF);
+                if (!f) break;
+                flow += f;
+            }
+        }
+    }
+
+    template<class E>
+    void bfs(const Graph<E> &g, int s) {
+        fill_n(level.begin(), V, -1);
+        queue<int> que;
+        level[s] = 0;
+        que.push(s);
+        while (!que.empty()) {
+            int v = que.front(); que.pop();
+            for (E e: g[v]) {
+                if (e.cap <= 0) continue;
+                if (level[e.to] < 0) {
+                    level[e.to] = level[v] + 1;
+                    que.push(e.to);
+                }
+            }
+        }
+    }
+
+    template<class E>
+    T dfs(Graph<E> &g, int v, int t, T f) {
+        if (v == t) return f;
+        for (int &i = iter[v]; i < (int)g[v].size(); i++) {
+            E &e = g[v][i];
+            if (e.cap <= 0) continue;
+            if (level[v] < level[e.to]) {
+                T d = dfs(g, e.to, t, min(f, e.cap));
+                if (d <= 0) continue;
+                e.cap -= d;
+                g[e.to][e.rev].cap += d;
+                return d;
+            }
+        }
+        return 0;
+    }
+};
Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,2 @@`
	`1`	`+template <class E>`
	`2`	`+using Graph = vector<vector<E>>;`