图论模板

并查集

struct dsu {
private:
    // number of nodes
    int n;
    // root node: -1 * component size
    // otherwise: parent
    std::vector<int> pa;
public:
    dsu(int n_ = 0) : n(n_), pa(n_, -1) {}
    // find node x's parent
    int find(int x) {
        return pa[x] < 0 ? x : pa[x] = find(pa[x]);
    }
    // merge node x and node y 
    // if x and y had already in the same component, return false, otherwise return true
    // Implement (union by size) + (path compression)
    bool unite(int x, int y) {
        int xr = find(x), yr = find(y);
        if (xr != yr) {
            if (-pa[xr] < -pa[yr]) std::swap(xr, yr);
            pa[xr] += pa[yr];
            pa[yr] = xr; // y -> x
            return true;
        }
        return false;
    }
    // size of the connected component that contains the vertex x
    int size(int x) {
        return -pa[find(x)];
    }
};

最短路

namespace Dijkstra {
#define ll long long
    static constexpr ll INF = 1e18;
    int n, m; // 点数 边数
    struct edge {
        int to;  // 点
        ll val; // 边权
        edge(int to_ = 0, ll val_ = 0) :to(to_), val(val_) {}
        bool operator < (const edge& k) const { return val > k.val; }
    };
    vector<vector<edge>> g;
    void init() { // 建图操作需要根据题意修改
        cin >> n >> m;
        g.resize(n);
        for (int i = 0; i < m; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            --u, --v;
            g[u].push_back(edge(v, w));
        }
    }
    ll dijkstra(int s, int t) { // 最短路
        vector<ll> dis(n, INF);
        vector<bool> vis(n, false);
        dis[s] = 0;
        priority_queue<edge> pq;
        pq.push(edge(s, 0));
        while (!pq.empty()) {
            auto top = pq.top();
            pq.pop();
            if (!vis[top.to]) {
                vis[top.to] = true;
                for (auto nxt : g[top.to]) {
                    if (!vis[nxt.to] && dis[nxt.to] > nxt.val + dis[top.to]) {
                        dis[nxt.to] = nxt.val + dis[top.to];
                        pq.push(edge(nxt.to, dis[nxt.to]));
                    }
                }
            }
        }
        return dis[t];
    }
#undef ll
}

最小生成树

struct edge {
    int u, v;
    int w;
    edge(int u_ = 0, int v_ = 0, int w_ = 0) :u(u_), v(v_), w(w_) {}
    bool operator< (const edge& k) const {
        return w < k.w;
    }
};
long long kruskal() { // kruskal算法 需要并查集
    int n, m;
    cin >> n >> m;
    dsu u(n);
    vector<edge> g(m);
    for (auto& i : g) {
        cin >> i.u >> i.v >> i.w;
        --i.u, --i.v;
    }
    sort(g.begin(), g.end());
    long long res = 0;
    for (auto i : g) {
        if (u.unite(i.u, i.v)) {
            res += i.w;
        }
    }
    return res;
}

最小树形图

namespace ZL {
    // a 尽量开大, 之后的边都塞在这个里面
    const int N = 100010, M = 100010, inf = 1e9;
    struct edge {
        int u, v, w, use, id;
        edge(int u_ = 0, int v_ = 0, int w_ = 0, int use_ = 0, int id_ = 0)
            : u(u_), v(v_), w(w_), use(use_), id(id_) {}
    }b[M], a[2000100];
    int n, m, ans, pre[N], id[N], vis[N], root, In[N], h[N], len, way[M];
    // 从root 出发能到达每一个点的最小树形图
    // 先调用init 然后把边add 进去, 需要方案就getway, way[i] 为1 表示使用
    // 最小值保存在ans
    void init(int _n, int _root) { // 点数 根节点
        n = _n; m = 0; b[0].w = inf; root = _root;
    }
    void add(int u, int v, int w) {
        m++;
        b[m] = edge(u, v, w, 0, m);
        a[m] = b[m];
    }
    int work() {
        len = m;
        for (;;) {
            for (int i = 1; i <= n; i++) { pre[i] = 0; In[i] = inf; id[i] = 0; vis[i] = 0; h[i] = 0; }
            for (int i = 1; i <= m; i++) {
                if (b[i].u != b[i].v && b[i].w < In[b[i].v]) {
                    pre[b[i].v] = b[i].u; In[b[i].v] = b[i].w; h[b[i].v] = b[i].id;
                }
            }
            for (int i = 1; i <= n; i++) if (pre[i] == 0 && i != root) return 0;
            int cnt = 0; In[root] = 0;
            for (int i = 1; i <= n; i++) {
                if (i != root) a[h[i]].use++; int now = i; ans += In[i];
                while (vis[now] == 0 && now != root) { vis[now] = i; now = pre[now]; }
                if (now != root && vis[now] == i) {
                    cnt++; int kk = now;
                    while (1) {
                        id[now] = cnt; now = pre[now];
                        if (now == kk) break;
                    }
                }
            }
            if (cnt == 0) return 1;
            for (int i = 1; i <= n; i++) if (id[i] == 0) id[i] = ++cnt;
            // 缩环, 每一条接入的边都会茶包原来接入的那条边, 所以要调整边权
            // 新加的边是u, 茶包的边是v
            for (int i = 1; i <= m; i++) {
                int k1 = In[b[i].v], k2 = b[i].v;
                b[i].u = id[b[i].u];
                b[i].v = id[b[i].v];
                if (b[i].u != b[i].v) {
                    b[i].w -= k1; a[++len].u = b[i].id; a[len].v = h[k2]; b[i].id = len;
                }
            }
            n = cnt; root = id[root];
        }
        return 1;
    }
    void getway() {
        for (int i = 1; i <= m; i++) way[i] = 0;
        for (int i = len; i > m; i--) { a[a[i].u].use += a[i].use; a[a[i].v].use -= a[i].use; }
        for (int i = 1; i <= m; i++) way[i] = a[i].use;
    }
}

最近公共祖先/倍增LCA

constexpr int SIZE = 200010;
constexpr int DEPTH = 21; // 最大深度 2^DEPTH - 1
int pa[SIZE][DEPTH], dep[SIZE];
vector<int> g[SIZE]; //邻接表
void dfs(int rt, int fin) { //预处理深度和祖先
    pa[rt][0] = fin;
    dep[rt] = dep[pa[rt][0]] + 1; //深度
    for (int i = 1; i < DEPTH; ++i) { // rt 的 2^i 祖先等价于 rt 的 2^(i-1) 祖先 的 2^(i-1) 祖先
        pa[rt][i] = pa[pa[rt][i - 1]][i - 1];
    }
    int sz = g[rt].size();
    for (int i = 0; i < sz; ++i) {
        if (g[rt][i] == fin) continue;
        dfs(g[rt][i], rt);
    }
}

int LCA(int x, int y) {
    if (dep[x] > dep[y]) swap(x, y);
    int dif = dep[y] - dep[x];
    for (int j = 0; dif; ++j, dif >>= 1) {
        if (dif & 1) {
            y = pa[y][j]; //先跳到同一高度
        }
    }
    if (y == x) return x;
    for (int j = DEPTH - 1; j >= 0 && y != x; --j) { //从底往上跳
        if (pa[x][j] != pa[y][j]) { //如果当前祖先不相等 我们就需要更新
            x = pa[x][j];
            y = pa[y][j];
        }
    }
    return pa[x][0];
}

二分图最大权匹配/KM

namespace KM {
    typedef long long ll;
    const int maxn = 510;
    const int inf = 1e9;
    int vx[maxn], vy[maxn], lx[maxn], ly[maxn], slack[maxn];
    int w[maxn][maxn]; // 以上为权值类型
    int pre[maxn], left[maxn], right[maxn], NL, NR, N;
    void match(int& u) {
        for (; u; std::swap(u, right[pre[u]]))
            left[u] = pre[u];
    }
    void bfs(int u) {
        static int q[maxn], front, rear;
        front = 0; vx[q[rear = 1] = u] = true;
        while (true) {
            while (front < rear) {
                int u = q[++front];
                for (int v = 1; v <= N; ++v) {
                    int tmp;
                    if (vy[v] || (tmp = lx[u] + ly[v] - w[u][v]) > slack[v])
                        continue;
                    pre[v] = u;
                    if (!tmp) {
                        if (!left[v]) return match(v);
                        vy[v] = vx[q[++rear] = left[v]] = true;
                    } else slack[v] = tmp;
                }
            }
            int a = inf;
            for (int i = 1; i <= N; ++i)
                if (!vy[i] && a > slack[i]) a = slack[u = i];
            for (int i = 1; i <= N; ++i) {
                if (vx[i]) lx[i] -= a;
                if (vy[i]) ly[i] += a;
                else slack[i] -= a;
            }
            if (!left[u]) return match(u);
            vy[u] = vx[q[++rear] = left[u]] = true;

        }

    }
    void exec() {
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j) {
                slack[j] = inf;
                vx[j] = vy[j] = false;
            }
            bfs(i);
        }
    }
    ll work(int nl, int nr) { // NL , NR 为左右点数, 返回最大权匹配的权值和
        NL = nl; NR = nr;
        N = std::max(NL, NR);
        for (int u = 1; u <= N; ++u)
            for (int v = 1; v <= N; ++v)
                lx[u] = std::max(lx[u], w[u][v]);
        exec();
        ll ans = 0;
        for (int i = 1; i <= N; ++i)
            ans += lx[i] + ly[i];
        return ans;
    }
    void output() { // 输出左边点与右边哪个点匹配, 没有匹配输出0
        for (int i = 1; i <= NL; ++i)
            printf("%d ", (w[i][right[i]] ? right[i] : 0));
        printf("\n");
    }
}

2-sat

/*
 * 2-sat
 * n 表示限制个数, i 为取(真), i+n 为不取(假)
 * 先初始化再建图
 * 建图时 若输入两组或关系 ((x = a) || (y = b))则有:
   if (a && b) {
       Twosat::add(x + n, y), Twosat::add(y + n, x);
   } else if (!a && b) {
       Twosat::add(x, y), Twosat::add(y + n, x + n);
   } else if (a && !b) {
       Twosat::add(x + n, y + n), Twosat::add(y, x);
   } else {
       Twosat::add(x, y + n), Twosat::add(y, x + n);
   }
 * 表示若条件1/2不成立 则条件2/1必定成立
 * 构造结果保存在 ans 数组 若ans[i] = 0则取i 否则取i+n
 * */
namespace Twosat {
    const int M = 4000010, N = 1000010;
    struct edge {
        int next, point;
        edge(int n_ = 0, int p_ = 0) :next(n_), point(p_) {}
    } e[M];
    int n, len, now, sign, head, sign2;
    int p[N << 1], dfs[N << 1], low[N << 1], where[N << 1];
    int s[N << 1], in[N << 1], ans[N], out[N << 1];
    void add(int k1, int k2) {
        e[++len] = edge(p[k1], k2);
        p[k1] = len;
    }
    void init(int _n) {
        n = _n;
        for (int i = 0; i <= n * 2 + 1; i++) {
            p[i] = where[i] = dfs[i] = low[i] = s[i] = in[i] = out[i] = 0;
        }
        len = now = sign = head = sign2 = 0;
    }
    void tarjan(int k1) {
        s[++head] = k1; in[k1] = 1; dfs[k1] = ++sign; low[k1] = sign;
        for (int i = p[k1]; i; i = e[i].next) {
            int j = e[i].point;
            if (dfs[j] == 0) {
                tarjan(j);
                low[k1] = min(low[k1], low[j]);
            } else if (in[j]) {
                low[k1] = min(low[k1], dfs[j]);
            }
        }
        if (dfs[k1] == low[k1]) {
            now++;
            while (1) {
                where[s[head]] = now;
                in[s[head]] = 0;
                out[s[head]] = ++sign2;
                head--;
                if (s[head + 1] == k1) {
                    break;
                }
            }
        }
    }
    int solve() { // ans[i] = 0 表示取i, 否则表示取i+n
        for (int i = 1; i <= n * 2; i++) {
            if (dfs[i] == 0) {
                tarjan(i);
            }
        }
        for (int i = 1; i <= n; i++) {
            if (where[i] == where[i + n]) {
                return 0;
            }
        }
        for (int i = 1; i <= n; i++) {
            if (out[i] < out[i + n]) {
                ans[i] = 0;
            } else {
                ans[i] = 1;
            }
        }
        return 1;
    }
}

最大团/Bron-Kerbosch

/*
 * 最大团 Bron-Kerbosch algorithm
 * 最劣复杂度 O(3^(n/3))
 * 采用位运算形式实现
 * */
namespace Max_clique {
#define ll long long
#define TWOL(x) (1ll<<(x))
    const int N = 60;
    int n, m;      // 点数 边数
    int r = 0;     // 最大团大小
    ll G[N];       // 以二进制形式存图
    ll clique = 0; // 最大团 以二进制形式存储
    void BronK(int S, ll P, ll X, ll R) { // 调用时参数这样设置: 0, TWOL(n)-1, 0, 0
        if (P == 0 && X == 0) {
            if (r < S) {
                r = S;
                clique = R;
            }
        }
        if (P == 0) return;
        int u = __builtin_ctzll(P | X);
        ll c = P & ~G[u];
        while (c) {
            int v = __builtin_ctzll(c);
            ll pv = TWOL(v);
            BronK(S + 1, P & G[v], X & G[v], R | pv);
            P ^= pv; X |= pv; c ^= pv;
        }
    }
    void init() {
        cin >> n >> m;
        for (int i = 0; i < m; i++) {
            int u, v;
            cin >> u >> v;
            --u, --v;
            G[u] |= TWOL(v);
            G[v] |= TWOL(u);
        }
        BronK(0, TWOL(n)-1, 0, 0);
        cout << r << ' ' << clique << '\n';
    }
}