Какие алгоритмы на графах знаете?cplus-54

#include <vector>
using Graph = std::vector<std::vector<int>>;

// Нумерованные вершины 0..n-1
Graph g(n);
g[0].push_back(1); // Ребро 0 → 1

#include <vector>
using AdjMatrix = std::vector<std::vector<bool>>;

AdjMatrix m(n, std::vector<bool>(n, false));
m[0][1] = true; // Ребро 0 → 1

void dfs(const Graph& g, int v, std::vector<bool>& visited) {
    visited[v] = true;
    for(int u : g[v]) {
        if(!visited[u]) {
            dfs(g, u, visited);
        }
    }
}

#include <queue>
void bfs(const Graph& g, int start) {
    std::vector<bool> visited(g.size(), false);
    std::queue<int> q;
    q.push(start);
    visited[start] = true;
    
    while(!q.empty()) {
        int v = q.front(); q.pop();
        for(int u : g[v]) {
            if(!visited[u]) {
                visited[u] = true;
                q.push(u);
            }
        }
    }
}

#include <queue>
using Pair = std::pair<int, int>; // вес, вершина

void dijkstra(const Graph& g, int start) {
    std::vector<int> dist(g.size(), INT_MAX);
    std::priority_queue<Pair, std::vector<Pair>, std::greater<Pair>> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while(!pq.empty()) {
        auto [d, v] = pq.top(); pq.pop();
        if(d > dist[v]) continue;
        
        for(auto& [u, w] : g[v]) {
            if(dist[u] > dist[v] + w) {
                dist[u] = dist[v] + w;
                pq.push({dist[u], u});
            }
        }
    }
}

void floydWarshall(std::vector<std::vector<int>>& dist) {
    int n = dist.size();
    for(int k = 0; k < n; ++k)
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
                if(dist[i][k] != INT_MAX && dist[k][j] != INT_MAX)
                    dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
}

#include <algorithm>
#include <numeric>

struct Edge { int u, v, w; };

int kruskal(std::vector<Edge>& edges, int n) {
    std::sort(edges.begin(), edges.end(), [](Edge a, Edge b) { return a.w < b.w; });
    
    std::vector<int> parent(n);
    std::iota(parent.begin(), parent.end(), 0);
    
    auto find = [&](int u) {
        while(parent[u] != u) u = parent[u] = parent[parent[u]];
        return u;
    };
    
    int total = 0;
    for(Edge e : edges) {
        int u_root = find(e.u);
        int v_root = find(e.v);
        if(u_root != v_root) {
            parent[v_root] = u_root;
            total += e.w;
        }
    }
    return total;
}

void kosaraju(const Graph& g) {
    int n = g.size();
    std::vector<int> order;
    std::vector<bool> visited(n, false);
    
    // Первый проход (топологическая сортировка)
    std::function<void(int)> dfs1 = [&](int v) {
        visited[v] = true;
        for(int u : g[v])
            if(!visited[u]) dfs1(u);
        order.push_back(v);
    };
    
    // Транспонирование графа
    Graph gT(n);
    for(int v = 0; v < n; ++v)
        for(int u : g[v])
            gT[u].push_back(v);
    
    // Второй проход
    std::vector<int> component(n);
    int current_component = 0;
    visited.assign(n, false);
    
    for(int v : order)
        if(!visited[v]) {
            std::stack<int> stack;
            stack.push(v);
            visited[v] = true;
            component[v] = current_component;
            
            while(!stack.empty()) {
                int u = stack.top(); stack.pop();
                for(int w : gT[u])
                    if(!visited[w]) {
                        visited[w] = true;
                        component[w] = current_component;
                        stack.push(w);
                    }
            }
            current_component++;
        }
}

bool bfs_fordFulkerson(const Graph& residual, int s, int t, std::vector<int>& parent) {
    std::vector<bool> visited(residual.size(), false);
    std::queue<int> q;
    q.push(s);
    visited[s] = true;
    parent[s] = -1;
    
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(int v = 0; v < residual.size(); ++v) {
            if(!visited[v] && residual[u][v] > 0) {
                if(v == t) {
                    parent[v] = u;
                    return true;
                }
                q.push(v);
                parent[v] = u;
                visited[v] = true;
            }
        }
    }
    return false;
}

int fordFulkerson(Graph& graph, int s, int t) {
    Graph residual = graph;
    std::vector<int> parent(graph.size());
    int max_flow = 0;
    
    while(bfs_fordFulkerson(residual, s, t, parent)) {
        int path_flow = INT_MAX;
        for(int v = t; v != s; v = parent[v]) {
            int u = parent[v];
            path_flow = std::min(path_flow, residual[u][v]);
        }
        
        for(int v = t; v != s; v = parent[v]) {
            int u = parent[v];
            residual[u][v] -= path_flow;
            residual[v][u] += path_flow;
        }
        
        max_flow += path_flow;
    }
    return max_flow;
}