1、快速排序

quickSort(int[] q, int l, int r) {
    if (l >= r) {
        return;
    }

    int i = l - 1;
    int j = r + 1;
    int x = q[l + r >> 1];

    while (i < j) {
        do i++; while (q[i] < x);
        do j--; while (q[j] > x);

        if (i < j) {
            int t = q[i];
            q[i] = q[j];
            q[j] = t;
        }
    }
    quickSort(q, l, j);
    quickSort(q, j + 1, r);
}

2、归并排序

mergeSort(int[] q, int l, int r) {
    if (l >= r) {
        return;
    }

    int mid = l + r >> 1;
    mergeSort(q, l, mid);
    mergeSort(q, mid + 1, r);

    int i = l;
    int j = mid + 1;
    int k = 0;
    int[] temp = new int[r - l + 1];

    while (i <= mid && j <= r) {
        if (q[i] < q[j]) {
            temp[k++] = q[i++];
        } else {
            temp[k++] = q[j++];
        }
    }

    while (i <= mid) {
        temp[k++] = q[i++];
    }
    while (j <= r) {
        temp[k++] = q[j++];
    }

    for (i = l, j = 0; i <= r; i++, j++) {
        q[i] = temp[j];
    } 
}

3、二分查找（整数二分）

int binarySearch(int[] q, int l, int r, int x) {
    while(l < r) {
        int mid = l + r >> 1;
        if (q[mid] >= x) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    if (q[l] == x) {
        return l;
    }
    return -1;
}

int binarySearch(int[] q, int l, int r, int x) {
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (q[mid] <= x) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    if (q[l] == x) {
        return l;
    }
    return -1;
}

4、二分查找（浮点数二分）

double binarySearch(double l, double r, double x) {
    while (r - l > 1e-8) {
        double mid = (l + r) / 2;
        if (mid * mid * mid > x) {
            r = mid;
        } else {
            l = mid;
        }
    }
    return l;
}

5、前缀合

s[i] = s[i - 1] + a[i];

6、子矩阵的和

s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + q[i][j];

// x2, y2 -> x1, y1
s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];

7、差分

void insert(int[] q, int l, int r, int c) {
    q[l] += c;
    q[r + 1] -= c; 
}

s[i] += s[i - 1];

8、差分矩阵

void insert(int[][] q, int x1, int y1, int x2, int y2 int c) {
    q[x1][y1] += c;
    q[x2 + 1][y1] -= c;
    q[x1][y2 + 1] -= c;
    q[x2 + 1][y2 + 1] += c; 
}

s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

9、双指针算法

//求最长连续不重复子序列
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int N = 100010;
        int[] a = new int[N];
        int[] s = new int[N];
        String[] line = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(line[i]);
        }

        int res = 0;
        for (int i = 0, j = 0; i < n; i++) {
            s[a[i]]++;
            while (s[a[i]] > 1) {
                s[a[j]]--;
                j++;
            }
            res = Math.max(res, i - j + 1);
        }

        System.out.print(res);
    }
}

// 数组元素的目标和
for (int i = 0; i < n; i++) {
    int j = m - 1;
    while (a[i] + b[j] > x && j >= 0) {
        j--;
    }
    if (a[i] + b[j] == x) {
        System.out.print(i + " " + j);
        break;
    }
}

// 判断子序列
int i = 0, j = 0;
for (; i < m && j < n; i++) {
    if (b[i] == a[j]) {
        j++;
    }
}
if (j == n) {
    System.out.print("Yes");
} else {
    System.out.print("No");
}

10、位运算

// 二进制中 1 的个数
int res = 0;
for (int i = 31; i >= 0; i--) {
    int ans = x >> i & 1;
    if (ans == 1) {
        res++;
    }
}

11、数组模拟单链表

static int N = 100010;
static int[] e = new int[N];
static int[] ne = new int[N];
static int idx = 0, head = -1;

public static void addToHead(int x) {
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx++;
}

public static void add(int k, int x) {
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}

public static void remove(int k) {
    ne[k] = ne[ne[k]];
}

12、数组模拟双链表

static int N = 100010;
static int[] e, l, r;
static int idx;

public static void init() {
    e = new int[N];
    l = new int[N];
    r = new int[N];

    r[0] = 1;
    l[1] = 0;
    idx = 2;
}

// 默认右插入
public static void add(int k, int x) {
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}

public static void remove(int k) {
    l[r[k]] = l[k];
    r[l[k]] = r[k];
}

13、数组模拟栈

static int N = 100010;
static int[] stk;
static int tt;

public static void init() {
    stk = new int[N];
    tt = -1;
}

public static void push(int x) {
    stk[++tt] = x;
}

public static void pop() {
    tt--;
}

public static boolean empty() {
    return tt < 0;
}

public static int query() {
    return stk[tt];
}

14、数组模拟队列

static int N = 100010;
static int[] q;
static int hh, tt;

public static void init() {
    q = new int[N];
    hh = 0;
    tt = -1;
}

public static void push(int x) {
    q[++tt] = x;
}

public static void pop() {
    hh++;
}

public static boolean empty() {
    return hh > tt;
}

public static int query() {
    return q[hh];
}

15、单调栈

for (int i = 0; i < n; i++) {
    while (tt != -1 && stk[tt] >= a[i]) {
        tt--;
    }
    if (tt < 0) {
        System.out.print("-1 ");
    } else {
        System.out.print(stk[tt] + " ");
    }
    stk[++tt] = a[i];
}

16、单调队列

q = new int[N];
hh = 0;
tt = -1;
for (int i = 0; i < n; i++) {
    // 维护队头，对头一定是等于 i - k + 1
    if (i - k + 1 > q[hh]) {
        hh++;
    }

    // 队列不为空，且队尾大于当前值，弹出队尾
    while (hh <= tt && a[q[tt]] >= a[i])  {
        tt--;
    }

    // 插入
    q[++tt] = i;

    // 滑动窗口初始化完成：i - k + 1 >= 0
    // 输出队头元素
    if (i - k + 1 >= 0) {
        bw.write(a[q[hh]] + " ");
    }
}

17、KMP

// 构造模式串的 next 数组
for (int i = 2, j = 0; i <= n; i++) {
    while (j > 0 && p[i] != p[j + 1]) {
        j = next[j];
    }

    if (p[i] == p[j + 1]) {
        j++;
    }

    next[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= m; i++) {
    while (j > 0 && s[i] != p[j + 1]) {
        j = next[j];
    }

    if (s[i] == p[j + 1]) {
        j++;
    }

    if (j == n) {
        j = next[j];
    }
}

18、Trie树

static int N = 100010;
static int[][] son = new int[N][26];
static int idx = 0;
static int[] cnt = new int[N];

public static void insert(char[] c) {
    int p = 0;
    for (int i = 0; i < c.length; i++) {
        int u = c[i] - 'a';
        if (son[p][u] == 0) {
            son[p][u] = ++idx;
        }
        p = son[p][u];
    }
    cnt[p]++;
}

public static int query(char[] c) {
    int p = 0;
    for (int i = 0; i < c.length; i++) {
        int u = c[i] - 'a';
        if (son[p][u] == 0) {
            return 0;
        } else {
            p = son[p][u];
        }
    }
    return cnt[p];
}

19、最大异或对

static int N = 3000010;
static int[][] son = new int[N][2];
static int idx = 0;

public static void insert(int x) {
    int p = 0;
    for (int i = 30; i >= 0; i--) {
        int u = x >> i & 1;
        if (son[p][u] == 0) {
            son[p][u] = ++idx;
        }
        p = son[p][u];
    }
}

public static int query(int x) {
    int p = 0;
    int res = 0;
    for (int i = 30; i >= 0; i--) {
        int u = x >> i & 1;
        if (son[p][1-u] != 0) {
            p = son[p][1-u];
            res += 1 << i;
        } else {
            p = son[p][u];
        }
    }
    return res;
}

20、并查集-合并集合

// 查询集合的根结点
// 压缩路径
public static int find(int x) {
    if (p[x] != x) {
        p[x] = find(p[x]);
    }
    return p[x];
}

// 初始化
for (int i = 1; i <= n; i++) {
    p[i] = i;
}

21、连通块的数量

// 维护size的并查集
// 约定集合的根结点的 size 表示这个集合的点的数量

import java.io.*;

public class Main {

    static int N = 100010;
    static int[] p = new int[N];
    static int[] size = new int[N];

    public static int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line1 = br.readLine().split(" ");
        int n = Integer.parseInt(line1[0]);
        int m = Integer.parseInt(line1[1]);

        for (int i = 1; i <= n; i++) {
            p[i] = i;
            size[i] = 1;
        }

        while (m-- > 0) {
            String[] line2 = br.readLine().split(" ");
            String op = line2[0];
            int a, b;

            if (op.equals("C")) {
                a = Integer.parseInt(line2[1]);
                b = Integer.parseInt(line2[2]);
                if (find(a) != find(b)) {
                    size[find(b)] += size[find(a)];
                }
                p[find(a)] = p[b];
            } else if (op.equals("Q1")) {
                a = Integer.parseInt(line2[1]);
                b = Integer.parseInt(line2[2]);
                if (find(a) == find(b)) {
                    System.out.println("Yes");
                } else {
                    System.out.println("No");
                }
            } else {
                a = Integer.parseInt(line2[1]);
                System.out.println(size[find(a)]);
            }
        }
    }
}

22、食物链

import java.io.*;

public class Main {

    static int N = 100010;
    static int[] p = new int[N];
    static int[] d = new int[N];

    public static int find(int x) {
        if (p[x] != x) {
            int t = find(p[x]);// 找到根
            d[x] += d[p[x]];// 当前值到父节点的距离 + 父节点到父父节点的距离
            p[x] = t;// 当前值赋值为根
        }
        return p[x];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line1 = br.readLine().split(" ");
        int n = Integer.parseInt(line1[0]);
        int k = Integer.parseInt(line1[1]);

        // 赋值p
        for (int i = 1; i <= n; i++) {
            p[i] = i;
        }

        int res = 0;
        while (k-- > 0) {
            String[] line2 = br.readLine().split(" ");
            int t = Integer.parseInt(line2[0]);
            int x = Integer.parseInt(line2[1]);
            int y = Integer.parseInt(line2[2]);

            if (x > n || y > n) {
                res++;
            } else {
                int px = find(x);
                int py = find(y);
                if (t == 1) {
                    // x 和 y 是同类
                    if (px == py && (d[x] - d[y]) % 3 != 0) {
                        // 同根，且x和y不是同类，假话
                        res++;
                    } else if (px != py) {
                        // 不同根，px 以 py 为根，px 到根的距离为 d[p[x]] = d[y] - d[x]，
                        // 这样 d[px] + d[x] - d[y] 模 3 就为 0，即是同类
                        p[px] = py;
                        d[px] = d[y] - d[x];
                    }
                } else {
                    if (px == py && (d[x] - d[y] - 1) % 3 != 0) {
                        // 同根，且x不吃y
                        res++;
                    } else if (px != py) {
                        // 不同根，px 以 py 为根，px 到根的距离为 d[px] = d[y] + 1 - d[x]，
                        // 这样 d[p[x]] + d[x] - d[y] - 1 模 3 就为 0，即是同类
                        p[px] = py;
                        d[px] = d[y] + 1 - d[x];
                    }
                }
            }
        }

        System.out.print(res);
    }
}

23、堆排序

// 思路，维护小顶堆，每次取堆顶元素，再删除堆顶元素，向下移动，得到新的最小值

import java.io.*;

public class Main {

    static int N = 100010;
    static int[] h = new int[N];
    static int size = 0;

    // down
    // 2 * k: k 节点的左子节点
    // 2 * k + 1: k 节点的右子节点
    public static void down(int k) {
        int t = k;
        if (2 * k <= size && h[2 * k] < h[t]) {
            // 存在左子节点，并且左子节点的值比当前节点的值小
            // 取 t 为左子节点
            t = 2 * k;
        }
        if (2 * k + 1 <= size && h[2 * k + 1] < h[t]) {
            // 存在右子节点，并且右子节点的值比当前节点的值小
            // 取 t 为右子节点
            t = 2 * k + 1;
        }

        // 如果 t 不为当前节点，表示需要 k 和 t 位置的值互换
        if (t != k) {
            int temp = h[t];
            h[t] = h[k];
            h[k] = temp;

            // 递归执行
            down(t);
        }
    }

    // up
    // k / 2: 当前节点 k 的 根节点
    public static void up(int k) {
        // 当前节点根节点不为0（防止循环），且根节点的值比当前节点的值大，说明当前节点需要up
        while (k / 2 > 0 && h[k / 2] > h[k]) {
            // 交换 k / 2 和 k 位置的值
            int temp = h[k / 2];
            h[k / 2] = h[k];
            h[k] = temp;

            // k 变为 k / 2，也即根节点
            k /= 2;
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line1 = br.readLine().split(" ");
        int n = Integer.parseInt(line1[0]);
        int m = Integer.parseInt(line1[1]);
        String[] line2 = br.readLine().split(" ");

        // 初始化 h、size
        for (int i = 1; i <= n; i++) {
            h[i] = Integer.parseInt(line2[i - 1]);
        }
        size = n;

        // 把除了堆最后一行的数，都 down 一遍，这样就能维护小根堆
        for (int i = n / 2; i != 0; i--) {
            down(i);
        }

        while(m-- > 0) {
            // 输出
            System.out.print(h[1] + " ");

            // 交换 根 和 末尾 的值，删除末尾元素
            int temp = h[1];
            h[1] = h[size];
            h[size] = temp;
            size--;

            // 根此时被换成了末尾的值，需要 down 根
            down(1);
        }
    }
}

24、数组模拟堆

// 据题意要求，求最小值，故维护一个小根堆

import java.io.*;

public class Main {

    static int N = 100010;
    static int[] h = new int[N];// h 小根堆
    static int[] ph = new int[N];// ph 存放第 k 个插入点的下标
    static int[] hp = new int[N];// hp 存放堆中点的插入顺序
    static int size = 0;

    public static void down(int k) {
        int t = k;
        if (2 * k <= size && h[2 * k] < h[t]) {
            t = 2 * k;
        }
        if (2 * k + 1 <= size && h[2 * k + 1] < h[t]) {
            t = 2 * k + 1;
        }

        if (t != k) {
            heapSwap(t, k);
            down(t);
        }
    }

    public static void up(int k) {
        while (k / 2 > 0 && h[k/2] > h[k]) {
            heapSwap(k/2, k);
            k /= 2;
        }
    }

    public static void swap(int[] q, int i, int j) {
        int t = q[i];
        q[i] = q[j];
        q[j] = t;
    }

    public static void heapSwap(int i, int j) {
        swap(ph, hp[i], hp[j]);
        swap(hp, i, j);
        swap(h, i, j);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        size = 0;
        int m = 0;// 插入的个数

        while(n-- > 0) {
            String[] line = br.readLine().split(" ");
            String op = line[0];
            int k, x;

            if (op.equals("I")) {
                x = Integer.parseInt(line[1]);

                ++size;
                ++m;
                ph[m] = size;
                hp[size] = m;

                h[size] = x;
                up(size);
            } else if (op.equals("PM")) {
                System.out.println(h[1]);
            } else if (op.equals("DM")) {
                heapSwap(1, size);
                size--;
                down(1);
            } else if (op.equals("D")) {
                k = Integer.parseInt(line[1]);

                k = ph[k];

                heapSwap(k, size);
                size--;
                down(k);
                up(k);
            } else if (op.equals("C")) {
                k = Integer.parseInt(line[1]);
                x = Integer.parseInt(line[2]);

                k = ph[k];
                h[k] = x;
                down(k);
                up(k);
            }
        }
    }
}

25、模拟散列表

// 寻找某个数的位置
public static int find(int x) {
    // 对 x 取模，防止 x 为负的情况
    int hash = (x % N + N) % N;
    // hash 位置的元素不为空，且该元素不为 x，即哈希冲突了
    while (h[hash] != null && h[hash] != x) {
        // 开放寻址，寻找下一个位置
        hash ++;
        // 如果移动到数组边界，强制移动到数组起始位置
        if (hash == N) {
            hash = 0;
        }
    }
    return hash;
}

26、字符串哈希

import java.io.*;

public class Main {

    static int N = 100010;
    static long[] p = new long[N];
    static long[] h = new long[N];


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line1 = br.readLine().split(" ");
        int n = Integer.parseInt(line1[0]);
        int m = Integer.parseInt(line1[1]);
        String str = br.readLine();
        int P = 131;

        p[0] = 1;

        for (int i = 1; i <= n; i++) {
            p[i] = p[i - 1] * P;
            h[i] = h[i - 1] * P + str.charAt(i - 1);
        }

        while (m-- > 0) {
            String[] line2 = br.readLine().split(" ");
            int l1 = Integer.parseInt(line2[0]);
            int r1 = Integer.parseInt(line2[1]);
            int l2 = Integer.parseInt(line2[2]);
            int r2 = Integer.parseInt(line2[3]);
            System.out.println(h[r1] - h[l1 - 1] * p[r1 - l1 + 1] == h[r2] - h[l2 - 1] * p[r2 - l2 + 1] ?
                "Yes" : "No");
        }
    }
}

27、DFS-排列数字

public static void dfs(int u) {
    if (u == n) {
        for (int i = 0; i < n; i++) {
            System.out.print(path[i] + " ");
        }
        System.out.println();
    }

    for (int i = 1; i <= n; i++) {
        if (!st[i]) {
            path[u] = i;
            st[i] = true;
            dfs(u + 1);
            st[i] = false;
        }
    }
}

28、n-皇后问题

import java.io.*;

public class Main {

    static int N = 100;
    static int n;
    static char[][] g = new char[N][N];
    static boolean[] col = new boolean[N];
    static boolean[] dg = new boolean[N];
    static boolean[] udg = new boolean[N];

    public static void dfs(int u) {
        if (u == n) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    System.out.print(g[i][j]);
                }
                System.out.println();
            }
            System.out.println();
        }

        for (int i = 0; i < n; i++) {
            if (!col[i] && !dg[i + u] && !udg[i - u + n]) {
                g[u][i] = 'Q';
                col[i] = dg[i + u] = udg[i - u + n] = true;
                dfs(u + 1);
                col[i] = dg[i + u] = udg[i - u + n] = false;
                g[u][i] = '.';
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                g[i][j] = '.';
            }
        }

        dfs(0);
    }
}

29、BFS-走迷宫

// 求最短路径
// 走迷宫，bfs，每次把每层要做的事都做一遍

import java.io.*;

public class Main {

    static int N = 110;
    static int n, m;

    // 地图
    static int[][] g = new int[N][N];
    // 距离
    static int[][] d = new int[N][N];
    // 向量 x
    static int[] dx = new int[]{-1, 0, 1, 0};
    // 向量 y
    static int[] dy = new int[]{0, 1, 0, -1};
    // 队列
    static Pair[] q = new Pair[N * N];
    // 队列头、尾
    static int hh, tt;


    public static int bfs() {
        // 初始化 距离，都为 -1
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                d[i][j] = -1;
            }
        }
        // 第一个点的距离为 0
        d[0][0] = 0;
        // 初始化队列，头为0，尾为0，队列中已有一个数
        hh = 0;
        tt = 0;
        q[0] = new Pair(0, 0);

        // 只要 队列不为空
        while (hh <= tt) {
            // 队头出队元素
            Pair t = q[hh++];

            // 易错点：这里要对四个方向都遍历一遍
            for (int i = 0; i < 4; i++) {
                // 计算移动后的点的位置
                int x = t.left + dx[i];
                int y = t.right + dy[i];

                // 如果点没有越界、且点可用（地图为0）、且点没用过（距离为 -1）
                if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) {
                    q[++tt] = new Pair(x, y);
                    d[x][y] = d[t.left][t.right] + 1;
                }
            }
        }

        return d[n - 1][m - 1];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line1 = br.readLine().split(" ");
        n = Integer.parseInt(line1[0]);
        m = Integer.parseInt(line1[1]);

        for (int i = 0; i < n; i++) {
            String[] line2 = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                g[i][j] = Integer.parseInt(line2[j]);
            }
        }

        System.out.print(bfs());
    }
}

class Pair {
    Integer left;
    Integer right;

    Pair(Integer _left, Integer _right) {
        left = _left;
        right = _right;
    }
}

30、BFS-八数码

// 求最少交换次数，bfs
// 本题难点在于如何存储状态、状态转移

import java.io.*;
import java.util.*;

public class Main {

    static Queue<String> q = new LinkedList<>();
    static Map<String, Integer> m = new HashMap<>();
    static int[] dx = new int[]{-1, 0, 1, 0};
    static int[] dy = new int[]{0, 1, 0, -1};

    public static int bfs(String start, String end) {
        q.offer(start);
        m.put(start, 0);

        while (q.size() > 0) {
            String str = q.poll();
            Integer distance = m.get(str);
            if (str.equals(end)) {
                return distance;
            }

            int k = str.indexOf('x');
            int x = k / 3;
            int y = k % 3;

            for (int i = 0; i < 4; i++) {
                int a = x + dx[i];
                int b = y + dy[i];

                if (a >= 0 && a < 3 && b >= 0 && b < 3) {
                    char[] c = str.toCharArray();
                    char temp = c[k];
                    c[k] = c[3*a+b];
                    c[3*a+b] = temp;
                    String nstr = new String(c);

                    if (m.get(nstr) == null) {
                        q.offer(nstr);
                        m.put(nstr, distance + 1);
                    }
                }
            }
        }

        if (m.get(end) != null) {
            return m.get(end);
        }
        return -1;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        String start = "";
        String end = "12345678x";
        for (int i = 0; i < line.length; i++) {
            if (!line[i].equals(" ")) {
                start += line[i];
            }
        }

        System.out.print(bfs(start, end));
    }
}

31、树与图的存储

// 邻接矩阵
g[a][b] 表示 a 到 b 的边

// 邻接表
int[] h, e, ne;
int idx;

void init() {
    idx = 0;
    h = new int[N];
    e = new int[N];
    ne = new int[N];

    Arrays.fill(h, -1);
}

void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

32、树与图的遍历

// 深度优先 DFS：
int dfs(int u) {
    st[u] = true;

    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) {
            dfs(j);
        }
    }
}

// 广度优先 BFS：
Queue<Integer> q;
st[1] = true;// 表示1号点已经被遍历过了
q.offer(1);

while (q.size() > 0) {
    int t = q.poll();

    for(int i = h[t]; i != -1; i = ne[i]) {
        int j = e[i];
        if(!st[j]) {
            st[j] = true;// 表示点j已经被遍历过了
            q.offer(j);
        }
    }
}

33、拓扑排序

bool topSort() {

    // 初始化队列，把入度为0的点都入队列
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i++) {
        if (d[i] == 0) {
            q[++tt] = i;
        }
    }

    while(hh <= tt) {
        int t = q[hh++];
        for(int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (--d[j] == 0) {
                q[++tt] = j;
            }
        }
    }

    // 所有点都入队了，说明存在拓扑排序，否则不存在
    return tt == n - 1;
}

34、朴素dijkstra算法
求 1 号点到 n 号点的最短路径，如果不存在就返回 -1
只适用于边权都为正的求最短路问题

int[][] g;// 存储每条边
int[] d;// 存储1号点到每个点的距离
boolean[] st;//每个点的最短路是否已确定
int maxValue = Integer.MAX_VALUE / 2;

int dijkstra() {
    Arrays.fill(d, maxValue);
    d[1] = 0;

    for(int i = 0; i < n - 1; i++) {

        // 在没确定最短路的点中，寻找距离最小的点
        int t = -1;
        for (int j = 1; j <= n; j++) {
            if(!st[j] && (t == -1 || d[t] > d[j])) {
                t = j;
            }
        }

        // 找到点 t，用 t 更新其他点的距离
        for (int j = 1; j <= n; j++) {
            d[j] = Math.max(d[j], d[t] + g[t][j]);
        }

        // t 的距离已确定
        st[t] = true;
    }

    if (d[n] == maxValue) {
        return -1;
    }
    return d[n];
}

35、堆优化的 dijkstra 算法

int n;// 点的数量
int[] h, w, e, ne;// 邻接表存储所有边
int idx;
int[] d;// 存储1号点到其他点的距离
boolean[] st;// 每个点的最短路径是否已确定
int maxValue = Integer.MAX_VALUE / 2;
PriorityQueue<int[]> q = new PriorityQueue<>((a1, b1) -> a1[0] - b1[0]); // first 存储距离，second 存储 节点编号

void init() {
    Arrays.fill(h, -1);
}

int dijkstra() {
    Arrays.fill(d, maxValue);
    d[1] = 0;
    q.offer(new int[]{0, 1});

    while (q.size() > 0) {
        int[] t = q.poll();
        int distance = t[0];
        int ver = t[1];

        if(st[ver]) {
            continue;
        }
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];
            if(d[j] > distance + w[i]) {
                d[j] = distance + w[i];
                q.offer(new int[]{d[j], j});
            }
        }
    }

    if (d[n] == maxValue) {
        return -1;
    }
    return d[n];
}

36、Bellman-Ford 算法
其实就是双重循环，判断是否存在松弛三角
边权如果为负数、且有边数限制的最短路问题

int n, m; // n 表示点数、m 表示边数
int[] d; // 存储 1 号点到每个点的距离
Edge[] edges;
int maxValue = Integer.MAX_VALUE / 2;

class Edge {
    int a, b, w;// a 表示出点，b 表示入点，w 表示边权

    Edge(int _a, int _b, int _w) {
        a = _a;
        b = _b;
        w = _w;
    }
}

int bellman-ford {
    Arrays.fill(d, maxValue);
    d[1] = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int a = edges[j].a;
            int b = edges[j].b;
            int w = edges[j].w;

            if (d[b] > d[a] + w) {
                d[b] = d[a] + w;
            }
        }
    }

    if (d[n] > maxValue / 2) {
        return -1;
    }
    return d[n];
}

37、spfa 算法（队列优化的 bellman-ford 算法）

int n; // 总点数
int[] h, e, ne, w;// 邻接表存储所有边
int idx;
int[] d;// 存储 1 号点到每个点的距离
boolean[] st;// 每个点的最短距离是否已确定
int maxValue = Integer.MAX_VALUE / 2;
int[] q;// 队列优化
int hh = 0, tt = -1;

int spfa() {
    Arrays.fill(d, maxValue);
    d[1] = 0;
    q[++tt] = 1;
    st[1] = true;

    while (hh <= tt) {
        int t = q[hh++];
        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (d[j] > d[t] + w[i]) {
                d[j] = d[t] + w[i];
                if (!st[j]) {
                    q[++tt] = j;
                    st[j] = true;
                }
            }
        }
    }

    if (d[n] > maxValue / 2) {
        return -1;
    }
    return d[n];
}

38、spfa 判断是否存在负环

int n;// 总点数
int[] h, w, e, ne;// 存储每一条边
int idx;
int[] d, cnt;// d 存储1号点到每个点的距离；cnt 存储1到x的最短路中经过的点数
boolean[] st;// 存储每个点是否在队列中

// 如果存在负环，则返回true，否则返回false
boolean spfa() {
    int[] q = new int[N];
    int hh = 0, tt = -1;

    for (int i = 1; i <= n; i++) {
        q[++tt] = i;
        st[i] = true;
    }

    while (hh <= tt) {
        int t = q[hh++];
        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (d[j] > d[t] + w[i]) {
                d[j]  = d[t] + w[i];

                // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) {
                    return true;
                }
                if (!st[j]) {
                    q[++tt] = j;
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

39、floyd 算法
求两个点之间最短路
其实就是三重循环 k、i、j
d[i, j] = min(d[i, j], d[i, k] + d[k, j])

int maxValue = Integer.MAX_VALUE / 2;

// 初始化
void init() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                d[i][j] = 0;
            } else {
                d[i][j] = maxValue;
            }
        }
    }
}

// 算法结束后，d[a][b] 表示 a 到 b 之间的最短距离
void floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

40、朴素版 prim 算法
求最小生成树

int n; // n 表示点数
int[][] g;// 邻接矩阵存储每条边
int[] d;// 存储其他点到当前最小生成树的距离
boolean[] st;// 每个点是否已经在生成树中
int maxValue = Integer.MAX_VALUE / 2;

// 如果图不连通，则返回 maxValue
// 否则返回最小生成树的树边权重之和
int prim() {
    Arrays.fill(d, maxValue);

    int res = 0;
    for (int i = 0; i < n; i++) {
        // 找到未确定的、且距离最小的点 j
        int t = -1;
        for (int j = 0; j < n; j++) {
            if (!st[j] && (t == -1 || d[t] > d[j])) {
                t = j;
            }
        }

        // i 不为 0、且 t 到最小生成树的距离无穷，无解
        if (i != 0 && d[t] == maxValue) {
            return maxValue;
        }

        // 更新 res
        if (i != 0) {
            res += d[t];
        }
        st[t] = true;// t 已在生成树中

        // 用 t 更新其他点到生成树的距离
        for (int j = 1; j <= n; j++) {
            d[j] = Math.min(d[j], g[t][j]);
        }
    }

    return res;
}

41、Kruskal 算法

int n, m;// n 表示点数，m 表示边数
int[] p;// 并查集的父节点数组
Edge[] egdes;// 存储边

class Edge {
    int a, b, w;

    Edge(int _a, int _b, int _w) {
        a = _a;
        b = _b;
        w = _w;
    }
}

// 并查集求根结点、压缩路径
int find(int x) {
    if (p[x] != x) {
        p[x] = find(p[x]);
    }
    return p[x];
}

int kruskal() {
    // 按边权 从小到大 所有边
    Arrays.fill(edges, new Edge(0, 0, Integer.MAX_VALUE));
    Arrays.sort(edges, Comparator.comparingInt(e->e.c));

    // 初始化并查集
    for (int i = 1; i <= n; i++) {
        p[i] = i;
    }

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i++) {
        int a = edges[i].a;
        int b = edges[i].b;
        int w = edges[i].w;

        a = find(a);
        b = find(b);
        // 如果两个连通块不连通，将这两个连通块合并
        if (a != b) {
            p[a] = b;
            res += w;
            cnt++;
        }
    }

    // 检查是否所有顶点都已连接（是否存在最小生成树）
    if (cnt < n - 1) {
        return maxValue;
    }
    return res;
}

42、染色法判别二分图

int n;// 总点数
int[] h, e, ne;// 邻接表存储图
int idx;
int[] color;// 表示每个点的颜色，-1表示未染色，0白，1黑

// u：当前节点，c 当前节点的颜色
boolean dfs(int u, int c) {
    color[u] = c;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (color[j] == -1) {
            if (!dfs(j, 1 - c)) {
                return false;
            }
        } else if (color[j] == c) {
            return false;
        }
    }
    return true;
}

boolean check() {
    Arrays.fill(color, -1);
    boolean flag = true;
    for (int i = 1; i <= n; i++) {
        if (color[i] == -1) {
            if (!dfs(i, 0)) {
                flag = false;
                break;
            }
        }
    }
    return flag;
}

43、匈牙利算法求二分图的最大匹配

int n1, n2;// n1表示第一个集合中的点数，n2表示第二个集合中的点数
int[] h, e, ne;// 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int idx;
int[] match;// 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
boolean[] st;// 表示第二个集合中的每个点是否已经被遍历过

boolean find(int x) {
    for (int i = h[x]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) {
            st[j] = true;
            if (match[j] == 0 || find(match[j])) {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}

// 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
void main(String[] args) {
    int res = 0;
    for (int i = 1; i <= n1; i++) {
        Arrays.fill(st, false);
        if (find(i)) {
            res++;
        }
    }
}