Graph

Tree

树链剖分

重链剖分

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
// get fa, siz, dep, son
vector<int>  fa(n + 1), siz(n + 1), dep(n + 1), son(n + 1);
auto dfs = [&](auto self, int u, int f) -> void {
    int s = 0;
    fa[u] = f;
    siz[u] = 1;
    dep[u] = dep[f] + 1;
    for (auto& v : tree[u]) {
        if (v != f) {
            self(self, v, u);
            siz[u] += siz[v];
            if (siz[v] > siz[s]) {
                s = v;
                son[u] = s;
            }
        }
    }
};
dfs(dfs, 1, 0);

// get dfn, top
int id = 0;
vector<int> top(n + 1), dfn(n + 1);
auto get = [&](auto self, int u, int t) -> void {
    top[u] = t;
    dfn[u] = ++id;
    if (son[u]) {
        self(self, son[u], t);
    }

    for (auto& v : tree[u]) {
        if (v != fa[u] && v != son[u]) {
            self(self, v, v);
        }
    }
};
get(get, 1, 1);// t = 1

author: Jiangly

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
struct HLD {
    int n;
    std::vector<int> siz, top, dep, parent, in, out, seq;
    std::vector<std::vector<int>> adj;
    int cur;
    
    HLD() {}
    HLD(int n) {
        init(n);
    }
    void init(int n) {
        this->n = n;
        siz.resize(n);
        top.resize(n);
        dep.resize(n);
        parent.resize(n);
        in.resize(n);
        out.resize(n);
        seq.resize(n);
        cur = 0;
        adj.assign(n, {});
    }
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    void work(int root = 0) {
        top[root] = root;
        dep[root] = 0;
        parent[root] = -1;
        dfs1(root);
        dfs2(root);
    }
    void dfs1(int u) {
        if (parent[u] != -1) {
            adj[u].erase(std::find(adj[u].begin(), adj[u].end(), parent[u]));
        }
        
        siz[u] = 1;
        for (auto &v : adj[u]) {
            parent[v] = u;
            dep[v] = dep[u] + 1;
            dfs1(v);
            siz[u] += siz[v];
            if (siz[v] > siz[adj[u][0]]) {
                std::swap(v, adj[u][0]);
            }
        }
    }
    void dfs2(int u) {
        in[u] = cur++;
        seq[in[u]] = u;
        for (auto v : adj[u]) {
            top[v] = v == adj[u][0] ? top[u] : v;
            dfs2(v);
        }
        out[u] = cur;
    }
    int lca(int u, int v) {
        while (top[u] != top[v]) {
            if (dep[top[u]] > dep[top[v]]) {
                u = parent[top[u]];
            } else {
                v = parent[top[v]];
            }
        }
        return dep[u] < dep[v] ? u : v;
    }
    
    int dist(int u, int v) {
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }
    
    int jump(int u, int k) {
        if (dep[u] < k) {
            return -1;
        }
        
        int d = dep[u] - k;
        
        while (dep[top[u]] > d) {
            u = parent[top[u]];
        }
        
        return seq[in[u] - dep[u] + d];
    }
    
    bool isAncester(int u, int v) {
        return in[u] <= in[v] && in[v] < out[u];
    }
    
    int rootedParent(int u, int v) {
        std::swap(u, v);
        if (u == v) {
            return u;
        }
        if (!isAncester(u, v)) {
            return parent[u];
        }
        auto it = std::upper_bound(adj[u].begin(), adj[u].end(), v, [&](int x, int y) {
            return in[x] < in[y];
        }) - 1;
        return *it;
    }
    
    int rootedSize(int u, int v) {
        if (u == v) {
            return n;
        }
        if (!isAncester(v, u)) {
            return siz[v];
        }
        return n - siz[rootedParent(u, v)];
    }
    
    int rootedLca(int a, int b, int c) {
        return lca(a, b) ^ lca(b, c) ^ lca(c, a);
    }
};

LCA

O(log)

倍增
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
struct STLCA {
    int n, m, root;
    vector<long long> dep;
    vector<vector<pair<int, long long>>> tree;
    vector<vector<int>> fa;

    STLCA() {}
    STLCA(int n, int root = 0) {
        init(n, root);
    }

    void init(int n, int root) {
        this->n = n;
        this->m = __lg(n) + 1;
        this->root = root;
        dep.assign(n, 0);
        tree.assign(n, {});
        fa.assign(n, vector<int>(m));
    }

    void addEdge(int u, int v, long long w = 1) {
        tree[u].push_back({ v, w });
    }

    void work() {
        auto dfs = [&](auto dfs, int u, int f) -> void {
            fa[u][0] = f;
            for (int j = 1; j < m; j++) {
                fa[u][j] = fa[fa[u][j - 1]][j - 1];
            }
            for (auto& [v, w] : tree[u]) {
                if (v != f) {
                    dep[v] = dep[u] + w;
                    dfs(dfs, v, u);
                }
            }
        };
        dfs(dfs, root, root);
    }

    int lca(int x, int y) {
        if (dep[x] < dep[y]) {
            swap(x, y);
        }
        for (int j = m - 1; j >= 0; j--) {
            if (dep[fa[x][j]] >= dep[y]) {
                x = fa[x][j];
            }
        }
        if (x == y) {
            return x;
        }
        for (int j = m - 1; j >= 0; j--) {
            if (fa[x][j] != fa[y][j]) {
                x = fa[x][j];
                y = fa[y][j];
            }
        }
        return fa[x][0];   
    }
};
树链剖分
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
int fa[N];
int dep[N];
int siz[N];
int son[N];
int top[N];
vector<int> tree[N];

void dfs(int u, int f) {
	fa[u] = f;
	siz[u] = 1;
	dep[u] = dep[f] + 1;
	for (auto v : tree[u]) {
		if (v != f) {
			dfs(v, u);
			siz[u] += siz[v];//计算子节点数
			if (siz[son[u]] < siz[v]) son[u] = v;//更新重边
		}
	}
}

void get_top(int u, int f) {
	top[u] = f;
	if (son[u]) get_top(son[u], f);//重边
	for (auto v : tree[u]) {
		if (!top[v]) { //# f 不一定是 v 的 父节点
			get_top(v, v);//轻边
		}
	}
}

// get_top(rt, rt);

int lca(int a, int b) {
	while (top[a] != top[b]) { //跳到同一条重边
		dep[top[a]] > dep[top[b]] ? a = fa[top[a]] : b = fa[top[b]];
	}
	return dep[a] < dep[b] ? a : b;//选择深度更小的节点
}

O(1)

dfn序

$$
lca(x, y) =
\begin{cases}
x & x = y\
[dfn_{x} + 1, dfn_{y}] 之间深度最小节点的父亲 & x \neq y
\end{cases}
$$

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
const int N = 5e5 + 10;
const int M = 20;

int n;// number of vertex
int tot;
int lg[N];
int dep[N];
int dfn[N];
int st[N][M];
vector<int> tree[N];

void dfs(int u, int f) {
    dfn[u] = ++tot;
    dep[u] = dep[f] + 1;
    st[dfn[u]][0] = f;
    for (auto& v : tree[u]) {
        if (v != f) {
            dfs(v, u);
        }
    }
}

int get(int x, int y) {
    return dfn[x] < dfn[y] ? x : y;
}

void init() {// !!!
    for (int i = 2; i <= n; i++) {
        lg[i] = lg[i >> 1] + 1;
    }
    // st
    for (int j = 1; j < M; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = get(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int lca(int x, int y) {
    if (x == y) {
        return x;
    }
    x = dfn[x];
    y = dfn[y];
    if (x > y) {
        swap(x, y);
    }
    x++;
    int k = lg[y - x + 1];
    return get(st[x][k], st[y - (1 << k) + 1][k]);
}

int dis(int x, int y) {
    return dep[x] + dep[y] - dep[lca(x, y)] * 2;
}
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
struct DfnLCA {
    int n, m, root;
    vector<int> lg;
    vector<int> dfn;
    vector<long long> dep;
    vector<vector<pair<int, long long>>> tree;
    vector<vector<int>> st;

    DfnLCA() {}
    DfnLCA(int n, int root = 0) {
        init(n, root);
    }

    void init(int n, int root) {
        this->n = n;
        this->m = __lg(n) + 1;
        this->root = root;
        lg.assign(n, -1);
        dfn.assign(n, 0);
        dep.assign(n, 0);
        tree.assign(n, {});
        st.assign(n, vector<int>(m));
        for (int i = 1; i < n; i++) {
            lg[i] = lg[i >> 1] + 1;
        }
    }

    void addEdge(int u, int v, long long w = 1) {
        tree[u].push_back({ v, w });
    }

    int select(int x, int y) {
        return dfn[x] < dfn[y] ? x : y;
    }

    void work() {
        int id = 0;
        auto dfs = [&](auto dfs, int u, int f) -> void {
            dfn[u] = id++;
            st[dfn[u]][0] = f;
            for (auto& [v, w] : tree[u]) {
                if (v != f) {
                    dep[v] = dep[u] + w;
                    dfs(dfs, v, u);
                }
            }
        };
        dfs(dfs, root, root);

        for (int j = 1; j < m; j++) {
            for (int i = 0; i + (1 << j) < n; i++) {
                st[i][j] = select(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    int lca(int x, int y) {
        if (x == y) {
            return x;
        }
        x = dfn[x];
        y = dfn[y];
        if (x > y) {
            swap(x, y);
        }
        x += 1;
        int k = lg[y - x + 1];
        return select(st[x][k], st[y - (1 << k) + 1][k]);
    }

    long long dis(int x, int y) {
        return dep[x] + dep[y] - dep[lca(x, y)] * 2;
    }
};
欧拉序

$$
lca(x, y) = [Euler_{x}, Euler_{y}] 之间深度最小的节点
$$

1
// to do

直径

两次 dfs 或者 dp 可求出

trick:

每次合并两个联通块（合并后仍为树），求直径

设连通块1的直径为 $d_{1}$ 端点为 $u_{1}, v_{1}$

设连通块2的直径为 $d_{2}$ 端点为 $u_{2}, v_{2}$

$d = max(d_{1}, d_{2}, dis(u_{1}, u_{2}), dis(u_{1}, v_{2}), dis(v_{1}, u_{2}), dis(v_{1}, v_{2}))$

然后更新端点即可

trick:

树上的点到树上某点的最远距离等于它到树直径两端点取 $max$

DSU on tree

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
vector<int> siz(n + 1, 1), son(n + 1);
auto dfs = [&](auto dfs, int u, int f) -> void {
    for (auto& v : tree[u]) {
        if (v != f) {
            dfs(dfs, v, u);
            siz[u] += siz[v];
            if (siz[v] >= siz[son[u]]) {
                son[u] = v;
            }
        }
    }
};
dfs(dfs, 1, 0);

i64 result = 0;
auto update = [&](auto update, int u, int f, int s) -> void {
	// 增加点 u 的信息
    // 计算result的贡献 
    
    for (auto& v : tree[u]) {
        if (v != f && v != s) {
            update(update, v, u, s);
        }
    }
};

auto restore = [&](auto restore, int u, int f) -> void {
    // 删减点 u 的信息
    for (auto& v : tree[u]) {
        if (v != f) {
            restore(restore, v, u);
        }
    }
};

auto calculate = [&](auto calculate, int u, int f, int op) -> void {
    for (auto& v : tree[u]) {
        if (v != f && v != son[u]) {
            calculate(calculate, v, u, 1);
        }
    }

    if (son[u]) {
        calculate(calculate, son[u], u, 0);
    }

    update(update, u, f, son[u]);
	// 获得点 u 答案 -> result

    if (op) {
        restore(restore, u, f);
        result = 0;
    }
};
calculate(calculate, 1, 0, 0);

TreeHash

判断一些树是否同构的时，我们常常把这些树转成哈希值储存起来，以降低复杂度。
$$
f(S) = \left( c + \sum_{x \in S} g(x) \right) \bmod m
$$

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
struct TreeHash {
    const int root;
    static const int mask;
    static const int delta; // f(u) = delta + sum(son(u))
    vector<unsigned int> key;
    vector<vector<int>> tree;
    TreeHash(int n, int rt) : root(rt) {
        key.assign(n, 0);
        tree.assign(n, {});
    }
    void addEdge(int u, int v) {
        tree[u].push_back(v);
    }
    unsigned int hash(unsigned int val) {
        // hash 设计
        val ^= mask;
        val ^= val << 13;
        val ^= val >> 7;
        val ^= val << 17;
        val ^= mask;
        return val;
    }
    void work() {
        auto dfs = [&](auto &&dfs, int u, int f) -> void {
            key[u] = delta;
            for (auto& v : tree[u]) {
                if (v != f) {
                    dfs(dfs, v, u);
                    key[u] += hash(key[v]);
                }
            }
        };
        dfs(dfs, root, root);
        // g(f(u) - g(son(u))) + f(son(u))
        auto dp = [&](auto& dp, int u, int f) -> void {
            for (auto& v : tree[u]) {
                if (v != f) {
                    key[v] += hash(key[u] - hash(key[v])); 
                    dp(dp, v, u);
                }
            }
        };
        dp(dp, root, root);
    }
};
const int TreeHash::mask = chrono::steady_clock::now().time_since_epoch().count();
const int TreeHash::delta = chrono::steady_clock::now().time_since_epoch().count();

2 - SAT

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
/*
 * 给定 n 个 bool 变量
 * 给定 m 个条件 [i = a or j = b] (a, b in { 0, 1 })
 * 求使得全部条件满足的构造
 * [a or b] -> [!a -> b] or [!b -> a]
 * 建图 
 * i + !a * n -> j + b * n
 * j + !b * n -> i + a * n
 */
struct Twosat { 
    const int n;
    vector<int> dfn, low, stk, scc;
    vector<vector<int>> graph;
    Twosat(int n) : n(n) {
        dfn.assign(n * 2 + 1, 0);
        low.assign(n * 2 + 1, 0);
        stk.assign(n * 2 + 1, 0);
        scc.assign(n * 2 + 1, 0);
        graph.assign(n * 2 + 1, {});
    }

    // [i = a or j = b]
    void addConstraint(int i, bool a, int j, bool b) {
        addEdge(i + !a * n, j + b * n);
        addEdge(j + !b * n, i + a * n);
    }

    void addEdge(int u, int v) {
        graph[u].push_back(v);
    }

    void tarjan(int u) {
        static int id = 0;
        dfn[u] = low[u] = ++id;
        stk.push_back(u);
        for (auto& v : graph[u]) {
            if (!dfn[v]) {
                tarjan(v);
                low[u] = min(low[u], low[v]);
            } else if (!scc[v]) {
                low[u] = min(low[u], dfn[v]);
            }
        }
        static int cnt = 0;
        if (dfn[u] == low[u]) {
            cnt += 1;
            int v;
            do {
                v = stk.back();
                stk.pop_back();
                scc[v] = cnt;
            } while (v != u);
        }
    }

    vector<int> work() {
        for (int i = 1; i <= n * 2; i++) {
            if (!dfn[i]) {
                tarjan(i);
            }
        }
        for (int i = 1; i <= n; i++) {
            if (scc[i] == scc[i + n]) {
                return {};
            }
        }
        vector<int> res(n + 1);
        for (int i = 1; i <= n; i++) {
            res[i] = scc[i] > scc[i + n];
        }
        return res;
    }
};

trick

  1. 判定某个变量的取值 （0， 1， ？）

    $i \rightarrow i + n$ 变量为 1，$i + n \rightarrow i$ 变量为 0，都不能到达即都有可能。

    复杂度 $O(n)$

  2. 固定选 $i$ 点，建边 $i \rightarrow inv(i)$

二分图

判定 （染色法）

一个无向图是二分图，当且仅当图中不存在奇环。

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
struct BipartiteGraph {
    const int n;
    vector<vector<int>> graph;

    BipartiteGraph(int n) : n(n) {
        graph.assign(n, {});
    }

    void addEdge(int u, int v) {
        graph[u].push_back(v);
    }

    bool check() {
        vector<int> vis(n, -1);
        auto dfs = [&](auto &&dfs, int u, int tag) -> bool {
            vis[u] = tag;
            for (auto& v : graph[u]) {
                if (vis[v] == -1) {
                    if (dfs(dfs, v, tag ^ 1)) {
                        return true;
                    }
                } else {
                    if (vis[v] != (tag ^ 1)) {
                        return true;
                    }
                }
            }
            return false;
        };

        for (int i = 0; i < n; i++) {
            if (vis[i] == -1) {
                if (dfs(dfs, i, 0)) {
                    return false;
                }
            }
        }
        return true;
    }
};

最大匹配 （匈牙利算法）

$O(nm)$

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
struct Hungary {
    const int n, m;
    vector<int> lm, rm; // 左右两边的 match
    vector<vector<int>> adj;
    Hungary(int n, int m) : n(n), m(m) {
        lm.assign(n, -1);
        rm.assign(m, -1);
        adj.assign(n, {});
    }

    // 左边向右边建边 (只用单向边)
    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }

    int work() {
        int tag = 0; // 时间戳， 这样不用清空 vis
        vector<int> vis(m);
        auto dfs = [&](auto dfs, int u) -> bool {
            for (auto& v : adj[u]) {
                if (vis[v] != tag) {
                    vis[v] = tag;
                    if (rm[v] == -1 || dfs(dfs, rm[v])) {
                        lm[u] = v;
                        rm[v] = u;
                        return true;
                    }
                }
            }
            return false;
        };

        int cnt = 0;
        for (int i = 0; i < n; i++) {
            tag += 1;
            if (dfs(dfs, i)) {
                cnt += 1;
            }
        }
        return cnt;
    }
};

trick

  1. （每个左边的点最多有两条边时）求字典序最小的最大匹配，work 处倒序枚举 $i$ 即可。

    在这种情况下，形成的是树或基环树（森林），对环上最小编号选一个最小匹配就可确定所有匹配。

König 定理

最小点覆盖：选最少的点，满足每条边至少有一个端点被选。

二分图中，最小点覆盖 $=$ 最大匹配。

将二分图点集分成左右两个集合，使得所有边的两个端点都不在一个集合。

最大独立集

最大独立集：选最多的点，满足两两之间没有边相连。

因为在最小点覆盖中，任意一条边都被至少选了一个顶点，所以对于其点集的补集，任意一条边都被至多选了一个顶点，所以不存在边连接两个点集中的点，且该点集最大

最大独立集: $n$ $-$ 最小点覆盖。

最小路径覆盖

给定有向无环图（$DAG$）选若干条不相交的路径把整个图覆盖，最少选几条。

把 $n$ 个点拆分为 $[1, n]$ 和 $[n + 1, 2n]$ 两部分，如果存在边 $(x, y)$ ，则建边 $(x, y + n)$ 。

答案为 $n$ $-$ 最大匹配。

Flow

MaxFlow

$dinic ; O(\sqrt{n}m)$ 

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
struct MaxFlow {
    using T = long long;

    struct Edge {
        int to;
        T cap;
        Edge(int to, T cap) : to(to), cap(cap) {}
    };

    int n;
    vector<Edge> e;
    vector<vector<int>> g;
    vector<int> cur, h;

    MaxFlow() {}
    MaxFlow(int n) {
        init(n);
    }

    void init(int n) {
        this->n = n;
        e.clear();
        g.assign(n, {});
        cur.resize(n);
        h.resize(n);
    }

    void addEdge(int u, int v, T c) {
        g[u].push_back(e.size());
        e.emplace_back(v, c);
        g[v].push_back(e.size());
        e.emplace_back(u, 0);
    }

    bool bfs(int s, int t) {
        h.assign(n, -1);
        h[s] = 0;
        queue<int> que;
        que.push(s);
        while (!que.empty()) {
            const int u = que.front();
            que.pop();
            for (const int& i : g[u]) {
                const auto& [v, c] = e[i];
                if (c > 0 && h[v] == -1) {
                    h[v] = h[u] + 1;
                    if (v == t) {
                        return true;
                    }
                    que.push(v);
                }
            }
        }
        return false;
    }

    T dfs(int u, int t, T f) {
        if (u == t) {
            return f;
        }
        auto r = f;
        for (int& i = cur[u]; i < int(g[u].size()); i++) {
            const int j = g[u][i];
            auto [v, c] = e[j];
            if (c > 0 && h[v] == h[u] + 1) {
                const auto a = dfs(v, t, min(r, c));
                e[j].cap -= a;
                e[j ^ 1].cap += a;
                r -= a;
                if (r == 0) {
                    return f;
                }
            }
        }
        return f - r;
    }

    T flow(int s, int t) {
        T ans = 0;
        while (bfs(s, t)) {
            cur.assign(n, 0);
            ans += dfs(s, t, numeric_limits<T>::max());
        }
        return ans;
    }

    vector<bool> minCut() {
        vector<bool> c(n);
        for (int i = 0; i < n; i++) {
            c[i] = (h[i] != -1);
        }
        return c;
    }
    
    struct Info {
        int from;
        int to;
        T cap;
        T flow;
    };

    // 获取所有边的信息
    vector<Info> edges() {
        vector<Info> info;
        for (int i = 0; i < e.size(); i += 2) {
            Info x;
            x.from = e[i + 1].to;
            x.to = e[i].to;
            x.cap = e[i].cap + e[i + 1].cap;
            x.flow = e[i + 1].cap;
            info.push_back(x);
        }
        return info;
    }
};

欧拉图

  1. 无向图是欧拉图当且仅当：
    • 非零度顶点是连通的
    • 顶点的度数都是偶数
  2. 无向图是半欧拉图当且仅当：
    • 非零度顶点是连通的
    • 恰有 2 个奇度顶点
  3. 有向图是欧拉图当且仅当：
    • 非零度顶点是强连通的
    • 每个顶点的入度和出度相等
  4. 有向图是半欧拉图当且仅当：
    • 非零度顶点是弱连通的
    • 至多一个顶点的出度与入度之差为 1
    • 至多一个顶点的入度与出度之差为 1
    • 其他顶点的入度和出度相等
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
struct Hierholzer {
    const int n;
    vector<int> path;
    vector<int> in, out;
    vector<vector<int>> adj;
    Hierholzer(int n) : n(n) {
        in.assign(n, 0);
        out.assign(n, 0);
        adj.assign(n, {});
    }
    void addEdge(int u, int v) {
        in[v] += 1;
        out[u] += 1;
        adj[u].push_back(v);
    }
    void work() {
        int s = 0;
        bool ok = true;
        int oic = 0, ooc = 0;
        for (int i = 0; i < n; i++) { // 判定是否存在欧拉路径
            if (in[i] != out[i]) {
                ok = false;
                if (in[i] == out[i] + 1) {
                    oic += 1;
                } else if (in[i] == out[i] - 1) {
                    ooc += 1; s = i;
                } else {
                    path.clear();
                    return;
                }
            }
        }
        if (!ok && (oic != 1 || ooc != 1)) {
            path.clear();
            return;
        }
        for (int i = 0; i < n; i++) { // 字典序最小对边排序
            sort(adj[i].begin(), adj[i].end());
        }
        vector<int> cur(n);
        auto dfs = [&](auto &&dfs, int u) -> void {
            for (int &i = cur[u]; i < adj[u].size();) {
                dfs(dfs, adj[u][i++]);
            }
            path.push_back(u);
        };
        dfs(dfs, s);
        reverse(path.begin(), path.end());
    }
};

Rings-counts

普通环计数

对于状态 $f(s,i)$，枚举下一个结点 $u$。若 $u$ 在集合 $s$ 中且是编号最小的那个（即起点），就将答案 $A$ 加上 $f(s,i)$。若 $u$ 不在 $s$ 中，就将 $f(s,i)$ 加上 $f(s\cup{u},u)$。

这样会把二元环（即重边）也算上，并且每个非二元环会被计算两次（因为固定起点可以向两个方向走），所以答案为 $\dfrac{A-m}2$，其中 $m$ 表示边数。时间复杂度 $O(2^nm)$。

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
int n, m;
cin >> n >> m;
vector<vector<int>> g(n);
for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    g[u].push_back(v);
    g[v].push_back(u);
}

vector f(n, vector<long long>(1 << n));
for (int i = 0; i < n; i++) {
    f[i][1 << i] = 1;
}

long long ans = 0;
for (int s = 0; s < (1 << n); s++) {
    int lowbit = s & (-s);
    for (int c = 0; c < n; c++) {
        if (f[c][s] == 0) { continue; }
        for (auto& v : g[c]) {
            int mask = (1 << v);
            if (mask < lowbit) { continue; }
            if ((s >> v) & 1) {
                if (lowbit == mask) {
                    ans += f[c][s];
                }
            } else {
                f[v][s | mask] += f[c][s];
            }
        }
    }
}
cout << (ans - m) / 2;

三元环计数

无向图三元环个数

我们规定从度数小的点指向度数大的点，度数相同就从编号小的点指向编号大的点。那么此时此图是一张有向无环图（DAG）。

枚举 u 和 u 指向的点 v，再在 v 指向的点中枚举 w，检验 u 是否与 w 相连即可。

$O(m\sqrt{m})$ 

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
int n, m;
cin >> n >> m;
vector<int> deg(n + 1);
vector<pair<int, int>> edge(m + 1);
for (int i = 1; i <= m; i++) {
    auto& [u, v] = edge[i];
    cin >> u >> v;
    deg[u] += 1;
    deg[v] += 1;
}
vector<vector<int>> adj(n + 1);
for (int i = 1; i <= m; i++) {
    auto& [u, v] = edge[i];
    if (deg[u] < deg[v] || (deg[u] == deg[v] && u < v)) {
        adj[u].push_back(v);
    } else {
        adj[v].push_back(u);
    }
}
int ans = 0;
vector<int> vis(n + 1);
for (int u = 1; u <= n; u++) {
    for (auto& v : adj[u]) {
        vis[v] = true;
    }
    for (auto& v : adj[u]) {
        for (auto& w : adj[v]) {
            if (vis[w]) {
                ans += 1;
            }
        }
    }
    for (auto& v : adj[u]) {
        vis[v] = false;
    }
}
cout << ans;