Floyd

$dist[k,i,j]$表示从$i$到$j$只经过$1$~$k$的最短路径，每次$k$++，新插入一个点。

求传递闭包

void floyd() {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                d[i][j] |= d[i][k] && d[k][j];
            }
        }
    }
}

求无向图最小环

const int N = 110;
int n, m;
int mp[N][N], dist[N][N];
int pos[N][N], path[N], cnt;
void get_path(int l, int r) {  // i~j之间不包括i和j的道路
    if (pos[l][r] == 0)
        return;
    int mid = pos[l][r];
    get_path(l, mid);
    path[cnt++] = mid;
    get_path(mid, r);
}
signed main() {
    cin >> n >> m;
    memmax(mp);
    rep(i, 1, n) mp[i][i] = 0;
    rep(i, 1, m) {
        int x, y, z;
        cin >> x >> y >> z;
        mp[x][y] = mp[y][x] = min(mp[x][y], z);
    }
    memcpy(dist, mp, sizeof mp);
    ll ans = INF;
    for (int k = 1; k <= n; k++) {
        //在插入第k个点之前，最短路最大为k-1
        //至少包含3个点的环所经过的点最大编号是K
        for (int i = 1; i < k; i++) {
            for (int j = i + 1; j < k; j++) {
                if ((ll)dist[i][j] + mp[i][k] + mp[k][j] < ans) {
                    ans = dist[i][j] + mp[i][k] + mp[k][j];
                    cnt = 0;          //有更小的环要清空路径
                    path[cnt++] = k;  // k->i->j->k
                    path[cnt++] = i;
                    get_path(i, j);
                    path[cnt++] = j;
                }
            }
        }
        // floyd
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    pos[i][j] = k;  //记录由哪个状态更新来
                }
            }
        }
    }
    if (ans == INF)
        cout << "No solution." << endl;
    else {
        for (int i = 0; i < cnt; i++)
            cout << path[i] << ' ';
    }
}

类Floyd

$dist[k,i,j]$表示从$i$到$j$，恰好经过$k$条边的最短路径。

$dist[a+b,i,j]\ =\ min\{dist[a,i,k]\ +\ dist[b,k,j]\},k\ =\ 1…n$

按边数拼接，具有结合律，因此可以用快速幂

/*  求从s到e经过k条边的最短路  */
const int N = 210;
int n, m, k, s, e;
int res[N][N], g[N][N];
map<int, int> mp;
//不会自我更新，相互独立，满足结合律
void mul(int c[][N], int a[][N], int b[][N]) {
    static int temp[N][N];
    memmax(temp); //类Floyd
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                temp[i][j] = min(temp[i][j], a[i][k] + b[k][j]);
            }
        }
    }
    memcpy(c, temp, sizeof temp);
}
void qmi() {
    memmax(res);
    for (int i = 1; i <= n; i++)
        res[i][i] = 0;
    while (k) {
        if (k & 1)
            mul(res, res, g);  // res = res * g;
        mul(g, g, g);          // g = g * g;
        k >>= 1;
    }
}
int main() {
    cin >> k >> m >> s >> e;  //从s到e经过k条边的最短路
    memmax(g);
    //类Floyd算法中有严格的边数限制，如果出现了i->j->i的情况其实在i->i中我们是有2条边的
    //要是我们初始化g[i][i]=0,那样就没边了，影响了类Floyd算法的边数限制！
    if (!mp.count(s))
        mp[s] = ++n;
    if (!mp.count(e))
        mp[e] = ++n;
    //点较多，边较少，实际用到的点也少，可以利用map离散化
    s = mp[s];
    e = mp[e];
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> c >> a >> b;
        if (!mp.count(a))
            mp[a] = ++n;
        if (!mp.count(b))
            mp[b] = ++n;
        a = mp[a];
        b = mp[b];
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    qmi();
    cout << res[s][e] << endl;
}

最小生成树

Prim

int prim() {        // O(n^2+m)
    memmax(dist);
    dist[1] = 0;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int t = -1;
        for (int j = 1; j <= n; j++) {
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }
        st[t] = 1;
        ans += dist[t];
        for (int j = 1; j <= n; j++) {
            dist[j] = min(dist[j], mp[t][j]);
        }
    }
    return ans;
}

Kruskal

const int N = 110, M = 210;     // O(mlogm)
int n, m, f[N];
struct Node {
    int x, y, w;
    bool operator<(const Node& a) const { return w < a.w; }
} s[M];
int find(int x) {
    if (x != f[x])
        f[x] = find(f[x]);
    return f[x];
}
signed main() {
    cin >> n >> m;
    rep(i, 1, n) f[i] = i;
    int ans = 0;
    rep(i, 1, m) {
        int x, y, z;
        cin >> x >> y >> z;
        s[i] = {x, y, z};
    }
    sort(s + 1, s + 1 + m);
    rep(i, 1, m) {
        auto& [x, y, w] = s[i];
        int fa = find(x), fb = find(y);
        if (fa != fb) {
            f[fa] = fb;
            ans += w;
        }
    }
    cout << ans << endl;
}

次小生成树

方法一：先求最小生成树，再枚举删去最小生成树中的边求解。$O(mlogm+nm)$

方法二：先求最小生成树，然后依次枚举非树边，然后将该边加入树中，同时从树中去掉一条边，使得最终的图仍是一棵树。则一定可以求出次小生成树。$O(m+n^2+mlogm)$

[HTML_REMOVED]  定理：一定存在一棵次小生成树与最小生成树只差一条边 (可用反证法)

方法二朴素做法：

1 求最小生成树，统计标记每条边是树边，还是非树边，同时把最小生成树建立出来
2 预处理任意两点间的边权最大值$dist[a][b]$
3 依次枚举所有非树边$w$,求$min(sum+w(新边)-dist[a][b](老边)) $
严格次小生成树：满足$w>dist[a$][b]，则还需求出任意两点之间的边权次大值$dist2[a][b]$

方法二：（倍增LCA优化）

const int N = 100010, M = 300010;
int n, m;
struct Edge {
    int a, b, w;
    bool used;
    bool operator<(const Edge& a) const { return w < a.w; }
} edge[M];
int f[N];
int head[N], ne[M], v[M], w[M], tot = 0;
void add(int x, int y, int z) {
    v[++tot] = y, w[tot] = z, ne[tot] = head[x], head[x] = tot;
}
int find(int x) {
    if (x != f[x])
        f[x] = find(f[x]);
    return f[x];
}
int dep[N], fa[N][18], d1[N][18], d2[N][18];
queue<int> q;
ll kruskal() {
    rep(i, 1, n) f[i] = i;
    sort(edge + 1, edge + 1 + m);
    ll res = 0;
    rep(i, 1, m) {
        int a = find(edge[i].a), b = find(edge[i].b), w = edge[i].w;
        if (a != b) {
            f[a] = b;
            res += w;
            edge[i].used = 1;
        }
    }
    return res;
}
void build() {  //建最小生成树
    mem(head);
    rep(i, 1, m) {
        if (edge[i].used) {
            int a = edge[i].a, b = edge[i].b, w = edge[i].w;
            add(a, b, w), add(b, a, w);
        }
    }
}
void bfs() {
    memmax(dep);
    dep[0] = 0, dep[1] = 1;
    q.push(1);
    while (q.size()) {
        int t = q.front();
        q.pop();
        for (int i = head[t]; i; i = ne[i]) {
            int j = v[i];
            if (dep[j] > dep[t] + 1) {
                dep[j] = dep[t] + 1;
                q.push(j);
                fa[j][0] = t;
                d1[j][0] = w[i], d2[j][0] = -INF;
                for (int k = 1; k <= 16; k++) {
                    int anc = fa[j][k - 1];
                    fa[j][k] = fa[anc][k - 1];
                    int distance[4] = {d1[j][k - 1], d1[anc][k - 1],
                                       d2[j][k - 1], d2[anc][k - 1]};
                    d1[j][k] = d2[j][k] = -INF;
                    for (int u = 0; u < 4; u++) {
                        int d = distance[u];
                        if (d > d1[j][k])
                            d2[j][k] = d1[j][k], d1[j][k] = d;
                        else if (d != d1[j][k] && d > d2[j][k])
                            d2[j][k] = d;  //注意是严格次小边
                    }
                }
            }
        }
    }
}
int lca(int a, int b, int w) {
    static int distance[N * 2];  // 向上跳的过程中，记录最大边和次大边
    int cnt = 0;
    if (dep[a] < dep[b])
        swap(a, b);
    for (int k = 16; k >= 0; k--) {
        if (dep[fa[a][k]] >= dep[b]) {
            distance[++cnt] = d1[a][k];
            distance[++cnt] = d2[a][k];
            a = fa[a][k];
        }
    }
    if (a != b) {
        for (int k = 16; k >= 0; k--) {
            if (fa[a][k] != fa[b][k]) {
                distance[++cnt] = d1[a][k];
                distance[++cnt] = d2[a][k];
                distance[++cnt] = d1[b][k];
                distance[++cnt] = d2[b][k];
                a = fa[a][k], b = fa[b][k];
            }
        }
        distance[++cnt] = d1[a][0];
        distance[++cnt] = d1[b][0];
    }
    int dist1 = -INF, dist2 = -INF;
    rep(i, 1, cnt) {
        int d = distance[i];
        if (d > dist1)
            dist2 = dist1, dist1 = d;
        else if (d != dist1 && d > dist2)
            dist2 = d;
    }
    if (w > dist1)
        return w - dist1;
    if (w > dist2)
        return w - dist2;
    return INF;
}
signed main() {
    cin >> n >> m;
    rep(i, 1, m) {
        int a, b, c;
        cin >> a >> b >> c;
        edge[i] = {a, b, c};
    }
    ll sum = kruskal();
    build();
    bfs();
    ll res = 1e18;
    rep(i, 1, m) {
        if (!edge[i].used) {
            int a = edge[i].a, b = edge[i].b, w = edge[i].w;
            res = min(res, sum + lca(a, b, w));
        }
    }
    cout << res << endl;
}

SPFA求负环

一：统计每个点入队的次数，如果某个点入队n次，则说明存在负环

二：统计当前每个点的最短路中所包含的边数，如果某点的最短路所包含的边数大于等于n，则说明存在负环（推荐）

玄学优化：当所有点的入队次数超过2n时，图中有很大可能存在负环

（当队列超时时，可以尝试换成栈）

bool spfa() {                                               // O(nm)
    vector<int> dist(n + 1), st(n + 1), cnt(n + 1);
    queue<int> q;
    rep(i, 1, n) {    // 假想超级源点向每个点建一条长度为0的边
        q.push(i);
        st[i] = 1;
    }
    while (q.size()) {
        auto t = q.front();
        q.pop();
        st[t] = 0;
        for (auto [v, w] : mp[t]) {
            if (dist[v] > dist[t] + w) {
                dist[v] = dist[t] + w;
                cnt[v] = cnt[t] + 1;
                if (cnt[t] >= n)  // 最短路所包含的边数大于等于n
                    return true;
                if (!st[v]) {
                    st[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    return false;
}

01分数规划

给定一张 L 个点、P 条边的有向图，每个点都有一个权值$ f[i]$，每条边都有一个权值$ t[i]$。求图中的一个环，使“环上各点的权值之和”除以“环上各边的权值之和”最大。(将点权合并到边上，具体怎么合并据题而定) (本题可转化为求最长路径,判断正环)

const int N = 1010;
int n, m, wf[N];
vector<vector<pii>> mp;
bool spfa(double mid) {
    vector<double> dist(n + 1);
    vector<bool> st(n + 1);
    vector<int> cnt(n + 1);
    queue<int> q;
    rep(i, 1, n) q.push(i), st[i] = 1;
    while (q.size()) {
        auto t = q.front();
        q.pop();
        st[t] = 0;
        for (auto [v, w] : mp[t]) {
            if (dist[v] < dist[t] + wf[t] - w * mid) {
                dist[v] = dist[t] + wf[t] - w * mid;
                cnt[v] = cnt[t] + 1;
                if (cnt[v] >= n)   // 若有重边,要判断入队次数，而不是松弛次数
                    return true;
                if (!st[v]) {
                    st[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    return false;
}
signed main() {
    cin >> n >> m;
    mp.assign(n + 1, vector<pii>());
    rep(i, 1, n) cin >> wf[i];
    rep(i, 1, m) {
        int x, y, z;
        cin >> x >> y >> z;
        mp[x].push_back({y, z});
    }
    double l = 0, r = 1010;
    while (r - l > 1e-4) {
        double mid = (l + r) / 2;
        if (spfa(mid))
            l = mid;
        else
            r = mid;
    }
    cout << fixed << setprecision(2) << r << endl;
}

差分约束

(1)求不等式组的可行解（等式可拆分为两个不等式）

源点需要满足的条件: 从源点出发，一定可以走到所有的边

[1] 先将每个不等式$X_i <= X_j + C_k$,转化成一条从$X_j$走到$X_i$,边权为$C_k$的边

[2] 找一个超级源点,使得该源点一定可以遍历到所有边

[3] 从源点求一遍单源最短路

​ 结果一: 如果存在负环, 则原不等式组一定无解

​ 结果二: 如果没有负环, 则$dist[i]$就是原不等式组的一个可行解

(2) 如何求最大值和最小值（指的是每个变量的最值）

结论1: 如果求最小值，则应该求最长路；如果求最大值，则应该求最短路

问题1：如何转化$X_i<=C$,$ C$是常数, 这类的不等式

​ 方法: 建立一个超级源点, $0$, 然后建立$0$->$I$, 长度是$C$的边

以求$X_i$的最大值为例：求所有从$X_i$出发, 构成的不等式链, $X_i<=X_j +C_1 <= X_k + C_1 + C_2 <= … <=C_1 + C_2 +…$所计算出的上界, 最终$X_i$的最大值等于所有上界的最小值(最短路)

若求$X_i$的最小值, 即求所有下界的最大值, 即求最长路（有正环时无解）

例题：给定$n$个区间$[a_i,b_i]$和$n$个整数$c_i$，构造一个集合$Z$，使得$\forall$$i\in[1,n]$，$Z$中满足$a_i<=x<=b_i$的整数$x$不少于$c_i$个。

[HTML_REMOVED]  求这样的整数集合$Z$最少包含多少个数。

const int N = 50010;
vector<vector<pii>> mp;
int spfa() {
    vector<int> dist(N, -INF);  // 最小值应求最长路
    vector<bool> st(N);
    queue<int> q;
    q.push(0);
    dist[0] = 0;
    while (q.size()) {
        auto t = q.front();
        q.pop();
        st[t] = 0;
        for (auto [v, w] : mp[t]) {
            if (dist[v] < dist[t] + w) {
                dist[v] = dist[t] + w;
                if (!st[v]) {
                    st[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    return dist[50001];
}
signed main() {
    int n;
    cin >> n;
    mp.assign(N, vector<pii>());
    rep(i, 1, 50001) {
        mp[i - 1].push_back({i, 0});    // S[i] >= S[i-1] + 0
        mp[i].push_back({i - 1, -1});   // S[i-1] >= S[i] - 1
    }
    rep(i, 1, n) {
        int a, b, c;
        cin >> a >> b >> c;
        a++, b++;   // 用到前缀和，需要把第0位空出来
        mp[a - 1].push_back({b, c});    // S[b] >= s[a-1] + c
    }
    cout << spfa() << endl;
}

最近公共祖先

倍增$LCA$

const int N = 4e4 + 10;
int n, m, root;
int fa[N][16];
vector<vector<int>> mp(N, vector<int>());
vector<int> dep(N, INF);
void bfs() {     // 预处理O(nlogn)
    dep[0] = 0;  // 哨兵, 防止跳过根节点
    queue<int> q;
    q.push(root);
    dep[root] = 1;
    while (q.size()) {
        auto t = q.front();
        q.pop();
        for (int v : mp[t]) {
            if (dep[v] > dep[t] + 1) {
                dep[v] = dep[t] + 1;
                q.push(v);
                fa[v][0] = t;
                rep(i, 1, 15) fa[v][i] = fa[fa[v][i - 1]][i - 1];
            }
        }
    }
}
int lca(int a, int b) {   // 查询O(logn)
    if (dep[a] < dep[b])
        swap(a, b);
    for (int i = 15; i >= 0; i--) {
        if (dep[fa[a][i]] >= dep[b])
            a = fa[a][i];
    }
    if (a == b)
        return a;
    for (int i = 15; i >= 0; i--) {
        if (fa[a][i] != fa[b][i]) {
            a = fa[a][i];
            b = fa[b][i];
        }
    }
    return fa[a][0];
}
signed main() {
    cin >> n;
    rep(i, 1, n) {
        int a, b;
        cin >> a >> b;
        if (b == -1) {
            root = a;
            continue;
        }
        mp[a].push_back(b);
        mp[b].push_back(a);
    }
    bfs();
    cin >> m;
    rep(i, 1, m) {
        int a, b;
        cin >> a >> b;
        cout << lca(a, b) << endl;
    }
}

$Tarjan$离线求$LCA$

在深度优先遍历时，将所有点分成三大类:

[1] 已经遍历过，且回溯过的点（标记为2）

[2] 正在搜索的分支（标记为1）

[3] 还未搜索到的点（仍为初始值0）

const int N = 2e4 + 10;            // O(n + m)
int n, m, f[N];
vector<int> dist(N), res(N), st(N);
vector<vector<pii>> mp;
vector<pii> query[N];  // first存查询的另外一个点，second存查询编号
int find(int x) {
    if (x != f[x])
        f[x] = find(f[x]);
    return f[x];
}
void dfs(int u, int fa) {
    for (auto [v, w] : mp[u]) {
        if (v == fa)
            continue;
        dist[v] = dist[u] + w;
        dfs(v, u);
    }
}
void tarjan(int u) {
    st[u] = 1;
    for (auto [v, w] : mp[u]) {
        if (!st[v]) {
            tarjan(v);
            f[v] = u;  // 回溯完才把子节点的祖宗更新为当前节点
        }
    }
    // 回溯时才用这个点来计算之前标记为2的点
    for (auto [y, id] : query[u]) {
        if (st[y] == 2) {
            int fa = find(y);
            res[id] = dist[u] + dist[y] - 2 * dist[fa];
        }
    }
    st[u] = 2;
}
signed main() {
    cin >> n >> m;
    mp.assign(n + 1, vector<pii>());
    rep(i, 1, n - 1) {
        int a, b, c;
        cin >> a >> b >> c;
        mp[a].push_back({b, c});
        mp[b].push_back({a, c});
    }
    rep(i, 1, m) {
        int a, b;
        cin >> a >> b;
        if (a != b) {
            query[a].push_back({b, i});
            query[b].push_back({a, i});
        }
    }
    rep(i, 1, n) f[i] = i;
    dfs(1, -1);
    tarjan(1);
    rep(i, 1, m) cout << res[i] << endl;
}

欧拉序列+$RMQ$

const int N = 500010, M = 30;
int n, m, root;
vector<vector<int>> mp;
int dfn[N << 1], dep[N << 1], cnt, pos[N], st[N << 1][M], lg[N << 1];
void dfs(int u, int fa) {  //O(n)
    dfn[++cnt] = u;        //欧拉序列(dfs序)
    pos[u] = cnt;          //每个点在欧拉序列中第一次出现的位置
    dep[u] = dep[fa] + 1;  //每个点的深度
    for (auto v : mp[u]) {
        if (v == fa)
            continue;
        dfs(v, u);
        dfn[++cnt] = u;
    }
}
void RMQ() {  //O(nlogn)
    lg[0] = -1;
    for (int i = 1; i <= cnt; i++)
        lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= cnt; ++i)
        st[i][0] = dfn[i];
    for (int j = 1; j <= lg[cnt]; j++) {
        for (int i = 1; i + (1 << j) - 1 <= cnt; i++) {
            int x = st[i][j - 1], y = st[i + (1 << j - 1)][j - 1];
            st[i][j] = dep[x] <= dep[y] ? x : y;
        }
    }
}
int query(int l, int r) { // O(1)
    if (l > r)
        swap(l, r);
    int len = r - l + 1;
    int k = lg[len];
    int x = st[l][k], y = st[r - (1 << k) + 1][k];
    return dep[x] <= dep[y] ? x : y;
}
signed main() {
    cin >> n >> m >> root;
    mp.assign(n + 1, vector<int>());
    rep(i, 1, n - 1) {
        int x, y;
        cin >> x >> y;
        mp[x].push_back(y);
        mp[y].push_back(x);
    }
    dfs(root, 0);
    RMQ();
    rep(i, 1, m) {
        int x, y;
        cin >> x >> y;
        cout << query(pos[x], pos[y]) << endl;
    }
}

$LCA$+树上差分

例题：$N$个节点，$N-1$条主要边和$M$条附加边，先切断一条主要边，再切断一条附加边，把图切成不相通的两部分，一共有多少种方案

做法：每条附加边和主要边构成一个环，给环上所有的主要边的边权加$1$，意味着切断该主要边后还需切$1$条附加边才能把图分成两部分。若边权为$0$，则在$M$条附加边任选一条即可，若边权大于$1$，则没有符合的方案。

const int N = 1e5 + 10;
int n, m;
vector<int> dep;
vector<vector<int>> mp;
int fa[N][17], d[N], ans;  // d为差分数组
void bfs() {
    dep.assign(n + 1, INF);
    dep[0] = 0, dep[1] = 1;
    queue<int> q;
    q.push(1);
    while (q.size()) {
        auto t = q.front();
        q.pop();
        for (auto v : mp[t]) {
            if (dep[v] > dep[t] + 1) {
                dep[v] = dep[t] + 1;
                q.push(v);
                fa[v][0] = t;
                for (int k = 1; k <= 16; k++) {
                    fa[v][k] = fa[fa[v][k - 1]][k - 1];
                }
            }
        }
    }
}
int lca(int a, int b) {
    if (dep[a] < dep[b])
        swap(a, b);
    for (int k = 16; k >= 0; k--) {
        if (dep[fa[a][k]] >= dep[b])
            a = fa[a][k];
    }
    if (a == b)
        return a;
    for (int k = 16; k >= 0; k--) {
        if (fa[a][k] != fa[b][k])
            a = fa[a][k], b = fa[b][k];
    }
    return fa[a][0];
}
int dfs(int u, int fa) {  // 返回值为以u为根的子树的点权之和
    int res = d[u];
    for (auto v : mp[u]) {
        if (v == fa)
            continue;
        int s = dfs(v, u);  // v子树的点权之和即为u-v这条边的边权
        if (s == 0)
            ans += m;
        else if (s == 1)
            ans++;
        res += s;
    }
    return res;
}
signed main() {
    cin >> n >> m;
    mp.assign(n + 1, vector<int>());
    rep(i, 1, n - 1) {
        int x, y;
        cin >> x >> y;
        mp[x].push_back(y), mp[y].push_back(x);
    }
    bfs();
    rep(i, 1, m) {
        int a, b;
        cin >> a >> b;
        int p = lca(a, b);
        d[a]++, d[b]++, d[p] -= 2;  // 给a~b的路径上的边的边权加1，差分在点上
    }
    dfs(1, -1);
    cout << ans << endl;
}

强连通分量

对每个点定义两个时间戳，$dfn[u]$表示遍历到$u$的时间戳，$low[u]$表示从$u$开始走，所能遍历到的最小时间戳

$u$是其所在的强连通分量的最高点，等价于$dfn[u]\ ==\ low[u]$

连通分量编号递减的顺序就是拓扑序

int dfn[N], low[N], num;
int stack[N], top;
bool ins[N];
int id[N], cnt;
vector<int> scc[N];
void tarjan(int x) {
    dfn[x] = low[x] = ++num;  // 时间戳
    stack[++top] = x, ins[x] = 1;
    for (int i = head[x]; i; i = ne[i]) {
        int j = v[i];
        if (!dfn[j]) {
            tarjan(j);
            low[x] = min(low[x], low[j]);
        } else if (ins[j]) {
            low[x] = min(low[x], dfn[j]);
        }
    }
    if (dfn[x] == low[x]) {    // 执行此操作时,x所在连通分量的后继已经遍历完了(dfs),因此编号递减就是拓扑序
        cnt++;
        int y;
        do {
            y = stack[top--], ins[y] = 0;
            id[y] = cnt, scc[cnt].push_back(y);
        } while (x != y);
    }
}
// main函数中:
for (int i = 1; i <= n; i++) {
    if (!dfn[i])
        tarjan(i);
}

有向图$Tarjan$缩点后，至少加几条边可以把整个图变成一个强连通分量

结论：若只有一个分量，不用加边。否则，入度为0的分量有$P$个，出度为0的分量有$Q$个，至少要加$max(P,Q)$条边

证明：不妨令$P<=Q$

①$P==1$时，从每个终点向起点加边，共$Q$条边。

②$P>1$时，$Q>=P>1$，必然存在起点$P_1$到$Q_1$，$P_2$到$Q_2(P_1!=P_2，Q_1!=Q_2)$，则从$Q_1$向$P_2$加边，这会导致$P$减一，$Q$减一。以此类推，当进行$P-1$次操作后$P$减为$1$，$Q$减为$Q-(P-1)$，即转化为了第①种情况，还需加$Q-(P-1)$条边，则一共需要加$(P-1)+Q-(P-1)\ =\ Q\ =\ max(P,Q)$条边

当$P<Q$时同理

最大半连通子图

半连通：对于任意两点$u$，$v$，存在$u->v$或$v->u$。[HTML_REMOVED]  子图：先选点，选出的点之间的所有边都要选(包括重边)

例题：求有向图$G$的最大半连通子图所拥有的节点数，以及不同的最大半连通子图的数目。

思路：缩点后建图，求最长链，由子图的定义知建图时应该对边判重，链上的权重是途径的连通分量的点的数量，按拓扑序递推即可。

const int N = 1e5 + 10;
int n, m, mod;
vector<vector<int>> mp, mps;
int dfn[N], low[N], num;
int stack[N], top;
bool ins[N];
int id[N], sz[N], cnt;
void tarjan(int x) {
    dfn[x] = low[x] = ++num;
    stack[++top] = x, ins[x] = 1;
    for (auto v : mp[x]) {
        if (!dfn[v]) {
            tarjan(v);
            low[x] = min(low[x], low[v]);
        } else if (ins[v]) {
            low[x] = min(low[x], dfn[v]);
        }
    }
    if (low[x] == dfn[x]) {
        cnt++;
        int y;
        do {
            y = stack[top--], ins[y] = 0;
            id[y] = cnt, sz[cnt]++;
        } while (x != y);
    }
}
signed main() {
    cin >> n >> m >> mod;
    mp.assign(n + 1, vector<int>());
    rep(i, 1, m) {
        int a, b;
        cin >> a >> b;
        mp[a].push_back(b);
    }
    rep(i, 1, n) {
        if (!dfn[i])
            tarjan(i);
    }
    mps.assign(cnt + 1, vector<int>());
    unordered_set<ll> s;  // 判重
    rep(i, 1, n) {
        for (auto v : mp[i]) {
            int a = id[i], b = id[v];
            ll hash = a * 1000000LL + b;     // 技巧：利用hash值
            if (a != b && s.count(hash) == 0) {
                mps[a].push_back(b);     // 建拓扑图
                s.insert(hash);
            }
        }
    }
    vector<int> f(cnt + 1), g(cnt + 1);  // 最多点数，方案数
    for (int i = cnt; i > 0; i--) {  // 依据拓扑序递推
        if (!f[i]) {
            f[i] = sz[i];
            g[i] = 1;
        }
        for (auto v : mps[i]) {
            if (f[v] < f[i] + sz[v]) {
                f[v] = f[i] + sz[v];
                g[v] = g[i];
            } else if (f[v] == f[i] + sz[v]) {
                g[v] = (g[v] + g[i]) % mod;
            }
        }
    }
    int maxn = 0, sum = 0;
    rep(i, 1, cnt) {
        if (f[i] > maxn) {
            maxn = f[i];
            sum = g[i];
        } else if (f[i] == maxn) {
            sum = (sum + g[i]) % mod;
        }
    }
    cout << maxn << endl << sum << endl;
}

双连通分量

桥：连通图中删去一条边，图不再连通，那条边就是桥

边双连通分量(e-DCC)：极大没有桥的连通块。性质：任意两点间存在两条边不相交的路径

割点：连通图中删去一个点，图不再连通，那个点就是割点

点双连通分量(v-DCC)：极大无割点的连通块。每个割点至少属于两个v-DCC

两割点之间不一定是桥，桥两端也不一定是割点。

无向图$Tarjan$缩点后，至少加（“叶节点”数+$1$）/$2$条边可以把整个图变成边双连通分量

边双连通分量

判断桥：$dfn[x]<low[j]$

void tarjan(int x, int fa) {
    dfn[x] = low[x] = ++num;
    stack[++top] = x;
    for (int i = head[x]; ~i; i = ne[i]) {
        int j = v[i];
        if (!dfn[j]) {
            tarjan(j, i);  // fa传的是编号i
            low[x] = min(low[x], low[j]);
            if (dfn[x] < low[j])        //重点：判断桥(不取等)
                is_bridge[i] = is_bridge[i ^ 1] = 1;  //两端都要标记
        } else if (i != (fa ^ 1))       //不是反向边
            low[x] = min(low[x], dfn[j]);
    }
    if (dfn[x] == low[x]) {
        ++cnt;
        int y;
        do {
            y = stack[top--];
            id[y] = cnt;
        } while (x != y);
    }
}

求割点

$DFS$过程中从点$x$遍历到点$y$，如果有$low[y]≥dfn[x]$，则：
① 如果$x$不是根节点，那么$x$是割点；
② 如果$x$是根节点，则至少存在两各个节点$y$，使得$low[y_i]≥dfn[x]$此时$x$才是割点。

void tarjan(int x) {
    dfn[x] = low[x] = ++num;
    int cnt = 0;
    for (int i = head[x]; i; i = ne[i]) {
        int j = v[i];
        if (!dfn[j]) {
            tarjan(j);
            low[x] = min(low[x], low[j]);
            if (x != root && dfn[x] <= low[j] && !st[x]) {
                mp.push_back(x);
                st[x] = 1;
            }
            if (x == root)
                cnt++;
        } else
            low[x] = min(low[x], dfn[j]);
    }
    if (root == x && cnt > 1 && !st[x]) {
        mp.push_back(x);
        st[x] = 1;
    }
}

点双连通分量

①每个割点单独作为一个点
②从每个$V-DCC$向其所包含的每个割点连边

int dfn[N], low[N], Time;
int stack[N], top;
int dcc_cnt;
vector<int> dcc[N];
bool cut[N];
int root;
void tarjan(int x) {
    dfn[x] = low[x] = ++Time;
    stack[++top] = x;
    // x是孤立点，自成一个dcc
    if (x == root && head[x] == 0) {
        dcc_cnt++;
        dcc[dcc_cnt].push_back(x);
        return;
    }
    int cnt = 0;  //记录连着几个连通块
    for (int i = head[x]; i; i = ne[i]) {
        int j = v[i];
        if (!dfn[j]) {
            tarjan(j);
            low[x] = min(low[x], low[j]);
            if (dfn[x] <= low[j]) {
                cnt++;
                //如果不是根节点-只要有一个分支他就是割点 || 如果是根节点 需要有两个分支才是割点
                if (x != root || cnt > 1)
                    cut[x] = 1;
                ++dcc_cnt;
                int y;
                do {
                    y = stack[top--];
                    dcc[dcc_cnt].push_back(y);
                } while (y != j);  //注意弹到j为止
                //当前最高点x还要被用在更高的包含u的旧连通块
                dcc[dcc_cnt].push_back(x);
            }
        } else {
            low[x] = min(low[x], dfn[j]);
        }
    }
}
// main函数中:
for (root = 1; root <= n; root++) {
    if (!dfn[root])
        tarjan(root);
}

例题：给定一个无向图，问最少在几个点上设置出口，可以使得不管其他哪个点坍塌，其余所有点都可以与某个出口连通。

// 1 无割点          放2个出口 方案数 *= C[cnt][2] = cnt*(cnt-1)/2
// 2 有割点 V-DCC度数==1 放1个出口 方案数 *= C[cnt-1][1] = cnt-1 (不包含割点)
// 3 有割点 V-DCC度数>=2 放0个出口 方案数 *= 1
const int N = 1010, M = 510;
typedef unsigned long long ull;
int n, m;
int head[N], v[M], ne[M], tot;
int dfn[N], low[N], Time;
int stack[N], top;
int dcc_cnt;
vector<int> dcc[N];
bool cut[N];
int root;
signed main() {
    cin >> m;
    for (int i = 1; i <= dcc_cnt; i++) {
        dcc[i].clear();
    }
    while (m--) {
        int a, b;
        cin >> a >> b;
        n = max(n, a), n = max(n, b);
        add(a, b), add(b, a);
    }
    for (root = 1; root <= n; root++) {
        if (!dfn[root])
            tarjan(root);
    }
    int res = 0;  //出口数
    ull num = 1;  //方案数
    for (int i = 1; i <= dcc_cnt; i++) {
        int cnt = 0;  //统计每个连通分量中割点的个数
        for (int j = 0; j < dcc[i].size(); j++) {
            if (cut[dcc[i][j]])
                cnt++;
        }
        if (cnt == 0) {
            if (dcc[i].size() > 1)
                res += 2, num *= dcc[i].size() * (dcc[i].size() - 1) / 2;
            else
                res++;
        } else if (cnt == 1) {
            res += 1, num *= dcc[i].size() - 1;
        }
    }
    printf("%d %llu\n", res, num);
}

二分图

二分图<->染色无矛盾<->不存在奇数环

匹配：在图论中，一个「匹配」是一个边的集合，其中任意两条边都没有公共顶点。

最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。不存在增广路径。

完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。显然，完美匹配一定是最大匹配（完美匹配的任何一个点都已经匹配，添加一条新的匹配边一定会与已有的匹配边冲突）。但并非每个图都存在完美匹配。

交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边……形成的路径叫交替路。

增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路。

增广路有一个重要特点：非匹配边比匹配边多一条。因此，研究增广路的意义是改进匹配。只要把增广路中的匹配边和非匹配边的身份交换即可。由于中间的匹配节点不存在其他相连的匹配边，所以这样做不会破坏匹配的性质。交换后，图中的匹配边数目比原来多了 1 条。

匈牙利算法

// match[j]=a,表示女孩j的现有配对男友是a                             O(nm),n表示点数,m表示边数
int match[N];
// st[]数组称为临时预定数组，st[j]=1表示一轮模拟匹配中，女孩j被男孩x预定了。
bool st[N];
//这个函数的作用是用来判断,如果加入x来参与模拟配对,会不会使匹配数增多(即找增广路)
bool find(int x) {
    //遍历自己喜欢的女孩
    for (int i = head[x]; i; i = ne[i]) {
        int j = v[i];
        if (!st[j])  //如果在这一轮模拟匹配中,这个女孩尚未被预定
        {
            st[j] = true;  //那x就预定这个女孩了
            //如果女孩j没有男朋友，或者她原来的男朋友能够预定其它喜欢的女孩。配对成功,更新match
            if (!match[j] || find(match[j])) {
                match[j] = x;
                return true;
            }
        }
    }
    //自己中意的全部都被预定了。配对失败。
    return false;
}
//记录最大匹配
int res = 0;
for (int i = 1; i <= n1; i++) {  // n1:二分图一侧点的数量
    //因为每次模拟匹配的预定情况都是不一样的所以每轮模拟都要初始化
    memset(st, 0, sizeof st);
    if (find(i))
        res++;
}

染色法判断二分图

// DFS版                               O(n+m),n表示点数,m表示边数
int n, m;
vector<vector<int>> mp;
vector<int> st;
bool dfs(int u, int color) {
    st[u] = color;
    for (auto t : mp[u]) {
        if (!st[t]) {
            if (!dfs(t, 3 - color))
                return false;
        } else if (color == st[t]) {
            return false;
        }
    }
    return true;
}
signed main() {
    cin >> n >> m;
    mp.resize(n + 1);
    st.resize(n + 1);
    rep(i, 1, m) {
        int a, b;
        cin >> a >> b;
        mp[a].push_back(b);
        mp[b].push_back(a);
    }
    bool flag = true;
    rep(i, 1, n) {
        if (!st[i]) {
            if (!dfs(i, 1)) {
                flag = false;
                break;
            }
        }
    }
    if (flag)  cout << "Yes" << endl;
    else  cout << "No" << endl;
}

// BFS版
bool bfs(int u) {
    int hh = 0, tt = 0;
    queue<pii> q;
    q.push_back({u, 1});
    st[u] = 1;
    while (q.size()) {
        auto t = q.front();
        int ver = t.first, c = t.second;
        for (int i = head[ver]; i; i = ne[i]) {
            int j = e[i];
            if (!st[j]) {
                st[j] = 3 - c;
                q.push_back({j, 3 - c});
            } else if (st[j] == c)
                return false;
        }
    }
    return true;
}

等价形式

最大匹配数 = 最小点覆盖 = 总点数 - 最大独立集 = 总点数 - 最小路径点覆盖

最小点覆盖：选出最少的点，覆盖所有边
最大独立集：选出最多的点，使得选出的点之间没有边(即去掉最少的点，破坏所有边)<->最小点覆盖<->最大匹配数
最小路径点覆盖：DAG中，用最少的互不相交的路径(点不相交)，将所有点覆盖。（总点数-最大匹配数）(可用拆点证明，一个点拆成出点和入点)

最小路径重复点覆盖：先求传递闭包，再在新图上求最小路径点覆盖。

+++

欧拉回路和欧拉路径

对于无向图，所有边都连通
(1)存在欧拉路径的充分必要条件：度数为奇数的点只能有0或2个
(2)存在欧拉回路的充分必要条件：度数为奇数的点只能有0个

对于有向图，所有边都连通
(1)存在欧拉路径的充分必要条件：要么所有点的入度均等于入度；要么除了两个点之外，其余所有点的出度等于入度，剩余的两个点：一个满足出度比入度多1(起点),另一个满足入度比出度多1(终点)
(2)存在欧拉回路的充分必要条件：所有点的出度均等于入度

例题：给定一张图，请你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。

const int N = 1e5 + 10, M = 4e5 + 10;
int head[N], ne[M], v[M], tot = 0;
bool st[M];
int ans[M / 2], cnt;
int din[N], dout[N], type, n, m;
void add(int x, int y) {
    v[tot] = y, ne[tot] = head[x], head[x] = tot++;
}
void dfs(int x) {
    for (int i = head[x]; ~i; i = head[x]) { //关键：用head[x]更新i,否则仍为n^2复杂度
        if (st[i]) {
            head[x] = ne[i];
            continue;
        }
        st[i] = 1;
        if (type == 1)
            st[i ^ 1] = 1;
        int t;
        if (type == 1) {
            t = i / 2 + 1;   // 求出边的编号
            if (i & 1)       // 反向边存为负数
                t = -t;
        } else {
            t = i + 1;
        }
        int j = v[i];
        head[x] = ne[i]; //删边
        dfs(j);
        ans[++cnt] = t;
    }
}
signed main() {
    cin >> type;
    cin >> n >> m;
    memset(head, -1, sizeof head);
    rep(i, 1, m) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        if (type == 1)
            add(b, a);
        din[b]++, dout[a]++;
    }
    if (type == 1) { //无向图度数和应为偶数
        rep(i, 1, n) {
            if ((din[i] + dout[i]) & 1) {
                puts("NO");
                return 0;
            }
        }
    } else { //有向图入度应等于出度
        rep(i, 1, n) {
            if (din[i] != dout[i]) {
                puts("NO");
                return 0;
            }
        }
    }
    rep(i, 1, n) {
        if (~head[i]) {
            dfs(i);
            break;
        }
    }
    if (cnt < m) { //图应该连通
        puts("NO");
        return 0;
    }
    cout << "YES" << endl;
    don(i, cnt, 1) cout << ans[i] << ' '; //栈中为倒序
}

输出字典序最小的欧拉路径

保证$u$的出边，从小到大排序，不论从哪个点出发，最后一定会回到这个点
先遍历$1$号点（编号从$1$到$n$），则$1$号点一定最后被加入欧拉路径。
因此只要按照从小到大的点的序号搜，就可以得到字典序最小的欧拉路径（最后逆序输出，最小的点会最后加入$ans$)

邻接矩阵版：

const int N = 510;
int n = 500, m;
int g[N][N];
int ans[N], cnt;
int d[N];
void dfs(int x) {
    rep(i, 1, n) {
        if (g[x][i]) {
            g[x][i]--, g[i][x]--;
            dfs(i);
        }
    }
    ans[++cnt] = x;
}
signed main() {
    while (m--) {
        int a, b;
        cin >> a >> b;
        g[a][b]++, g[b][a]++;
        d[a]++, d[b]++;
    }
    int st = 1;
    for (int i = 1; i <= n; i++) {
        //找到度数为奇数的点,若找不到则整个图为环,此时从1开始
        if (d[i] % 2) {
            st = i;
            break;
        }
    }
    dfs(st);
    don(i, cnt, 1) cout << ans[i] << '\n';
    cout << endl;
}

邻接表版（易于排序）

const int N = 1e5 + 10;
vector<int> g[N];
int n, m;
int din[N], dout[N];
stack<int> ans;
int st = 1;
int del[N];
void dfs(int x) {
    for (int i = del[x]; i < g[x].size(); i = del[x]) {
        del[x] = i + 1;
        dfs(g[x][i]);
    }
    ans.push(x);
}
signed main() {
    jiasu;
    cin >> n >> m;
    rep(i, 1, m) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        dout[a]++;
        din[b]++;
    }
    rep(i, 1, n) sort(g[i].begin(), g[i].end());
    int num1 = 0, num2 = 0;
    bool flag = false;
    rep(i, 1, n) {
        if (din[i] != dout[i]) {
            flag = true;
            if (din[i] == dout[i] - 1)
                st = i, num1++;
            if (dout[i] == din[i] - 1)
                num2++;
        }
    }
    if (flag && !(num1 == num2 && num1 == 1)) {
        cout << "No" << endl;
        return 0;
    }
    dfs(st);

    while (!ans.empty()) {
        cout << ans.top() << ' ';
        ans.pop();
    }
    cout << endl;
}

+++

杂题

拯救大兵瑞恩_(单源最短路+状态压缩+双端队列BFS)

$n行m列$，相邻两个单元可能互通，或有门和墙，每种门只能用一种钥匙来开。本题可以将二维坐标映射到一维建图，下面采用另一种做法：邻接矩阵第三维表示方向。

const int N = 12;
int n, m, p, k, s;
int mp[N][N][4];  // 第三维表示方向
int key[N][N];
int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};
bool st[N][N][1 << 10];
struct Node {
    int x, y, state, d;
};
int bfs() {
    deque<Node> q;
    q.push_back({1, 1, 0, 0});
    while (q.size()) {
        auto [x, y, state, d] = q.front();
        q.pop_front();
        if (x == n && y == m)
            return d;
        if (st[x][y][state])
            continue;
        st[x][y][state] = 1;
        if ((state | key[x][y]) != state) {  // 如果有新的钥匙
            q.push_front({x, y, state | key[x][y], d});  // 状态变化不增加路程，加到队头
        }
        for (int i = 0; i < 4; i++) {          // 互通 或 有这类门的钥匙
            if (mp[x][y][i] == 0 || mp[x][y][i] > 0 && state & (1 << mp[x][y][i] - 1)) {
                int a = x + dx[i], b = y + dy[i];
                if (a >= 1 && a <= n && b >= 1 && b <= m)
                    q.push_back({a, b, state, d + 1});
            }
        }
    }
    return -1;
}
signed main() {
    cin >> n >> m >> p >> k;
    rep(i, 1, k) {
        int x1, y1, x2, y2, z;
        cin >> x1 >> y1 >> x2 >> y2 >> z;
        for (int j = 0; j < 4; j++) {
            if (x1 + dx[j] == x2 && y1 + dy[j] == y2)
                mp[x1][y1][j] = mp[x2][y2][(j + 2) % 4] = (z == 0 ? -1 : z); // 墙标记为-1
        }
    }
    cin >> s;
    rep(i, 1, s) {
        int x, y, z;
        cin >> x >> y >> z;
        key[x][y] |= (1 << z - 1);
    }
    cout << bfs() << endl;
}