并查集

class DisjointSet{
public:
    unordered_map<int, int> father;
    unordered_map<int, int> rank;
    int num_of_sets = 0;
    void add(int x){
        if(!father.count(x)){
            father[x] = -1;
            rank[x] = 0;
            num_of_sets++;
        }
    }
    int find(int x) {
        if (father[x] == -1) return x;
        else return find(father[x]);
    }
    bool is_connected(int x,int y){
        return find(x) == find(y);
    }
    void merge(int x, int y){
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (rank[x] < rank[y]) {
            father[x] = y;
        }
        else {
            father[y] = x;
            if (rank[x] == rank[y]) rank[x]++;
        }
        num_of_sets--;
    }
    int get_num_of_sets(){
        return num_of_sets;
    }
};

拓扑排序

class Solution {
public:
    vector<vector<int>> edges; // 存储有向图
    vector<int> visited; // 标记每个节点的状态：0=未搜索，1=搜索中，2=已完成
    vector<int> result;  // 用数组来模拟栈
    bool valid = true; // 判断有向图中是否有环

    void dfs(int u) {
        visited[u] = 1; // 搜索其相邻节点, 只要发现有环，立刻停止搜索
        for (int v: edges[u]) {
            if (visited[v] == 0) {
                dfs(v); // 如果「未搜索」那么搜索相邻节点
                if (!valid) return;
            }
            else if (visited[v] == 1) {
                valid = false;  // 如果「搜索中」说明找到了环
                return;
            }
        }
        visited[u] = 2; // 将节点标记为「已完成」
        result.push_back(u); // 将节点入栈
    }

    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        edges.resize(numCourses);
        visited.resize(numCourses);
        for (const auto& info: prerequisites) {
            edges[info[1]].push_back(info[0]);
        }
        for (int i = 0; i < numCourses && valid; ++i) {
            if (!visited[i]) {  // 每次挑选一个「未搜索」的节点，开始进行深度优先搜索
                dfs(i);
            }
        }
        if (!valid) return {};
        reverse(result.begin(), result.end());
        return result;
    }
};

Floyd算法

const int INF = 1000000;
void floyd(vector<vector<int>>& dist) {
    int n = dist.size();
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            if (dist[i][k] != INF) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][j] > dist[i][k] + dist[k][j]) dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

Dijkstra算法

void Dijkstra(vector<vector<int>> graph, vector<int>& dist) {
    int n = graph.size();
    vector<bool> used(n, false);
    for (int i = 0; i < n; ++i) {
        // 在还未确定最短路的点中，寻找距离最小的点
        int x = -1;
        for (int y = 0; y < n; ++y) {
            if (!used[y] && (x == -1 || dist[y] < dist[x])) {
                x = y;
            }
        }
        // 用该点更新所有其他点的距离
        used[x] = true;
        for (int y = 0; y < n; ++y) {
            dist[y] = min(dist[y], dist[x] + graph[x][y]);
        }
    }
}