Graph Algorithm Specialist

// Unweighted graph
vector<vector<int>> adj(n);
adj[u].push_back(v);
adj[v].push_back(u);  // Undirected

// Weighted graph
vector<vector<pair<int,int>>> adj(n);  // {neighbor, weight}
adj[u].push_back({v, w});

// Time: O(V + E), Space: O(V)
vector<int> bfs(vector<vector<int>>& adj, int src) {
    int n = adj.size();
    vector<int> dist(n, -1);
    queue<int> q;
    dist[src] = 0;
    q.push(src);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist;
}

// BFS from multiple sources simultaneously
// Time: O(V + E), Space: O(V)
vector<int> multiSourceBFS(vector<vector<int>>& adj, vector<int>& sources) {
    int n = adj.size();
    vector<int> dist(n, -1);
    queue<int> q;
    for (int s : sources) { dist[s] = 0; q.push(s); }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); }
        }
    }
    return dist;
}

// Time: O(V + E), Space: O(V)
vector<int> bfs01(vector<vector<pair<int,int>>>& adj, int src) {
    int n = adj.size();
    vector<int> dist(n, INT_MAX);
    deque<int> dq;
    dist[src] = 0;
    dq.push_front(src);
    while (!dq.empty()) {
        int u = dq.front(); dq.pop_front();
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (w == 0) dq.push_front(v);
                else dq.push_back(v);
            }
        }
    }
    return dist;
}

// Time: O(V + E), Space: O(V)
void dfs_iterative(vector<vector<int>>& adj, int src) {
    int n = adj.size();
    vector<bool> visited(n, false);
    stack<int> st;
    st.push(src);
    while (!st.empty()) {
        int u = st.top(); st.pop();
        if (visited[u]) continue;
        visited[u] = true;
        for (int v : adj[u])
            if (!visited[v]) st.push(v);
    }
}

// For subtree queries. Time: O(V + E)
int timer = 0;
vector<int> tin, tout;

void dfs(vector<vector<int>>& adj, int u, int parent) {
    tin[u] = timer++;
    for (int v : adj[u])
        if (v != parent) dfs(adj, v, u);
    tout[u] = timer++;
}

bool isAncestor(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

// Time: O(V + E), Space: O(V)
int countComponents(int n, vector<vector<int>>& adj) {
    vector<bool> visited(n, false);
    int components = 0;
    function<void(int)> dfs = [&](int u) {
        visited[u] = true;
        for (int v : adj[u]) if (!visited[v]) dfs(v);
    };
    for (int i = 0; i < n; i++)
        if (!visited[i]) { dfs(i); components++; }
    return components;
}

// Non-negative weights. Time: O((V + E) log V)
vector<long long> dijkstra(vector<vector<pair<int,int>>>& adj, int src) {
    int n = adj.size();
    vector<long long> dist(n, LLONG_MAX);
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
    dist[src] = 0;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

// Handles negative weights, detects negative cycles
// Time: O(V * E), Space: O(V)
struct Edge { int from, to, weight; };

pair<vector<long long>, bool> bellmanFord(int n, vector<Edge>& edges, int src) {
    vector<long long> dist(n, LLONG_MAX);
    dist[src] = 0;
    for (int i = 0; i < n - 1; i++) {
        bool updated = false;
        for (auto& [u, v, w] : edges) {
            if (dist[u] != LLONG_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                updated = true;
            }
        }
        if (!updated) break;
    }
    bool hasNegCycle = false;
    for (auto& [u, v, w] : edges)
        if (dist[u] != LLONG_MAX && dist[u] + w < dist[v]) { hasNegCycle = true; break; }
    return {dist, hasNegCycle};
}

// Time: O(V^3), Space: O(V^2)
void floydWarshall(vector<vector<long long>>& dist, int n) {
    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] != LLONG_MAX && dist[k][j] != LLONG_MAX)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

// Time: O(E log E), Space: O(V)
class UnionFind {
    vector<int> parent, rank_;
public:
    UnionFind(int n) : parent(n), rank_(n, 0) { iota(parent.begin(), parent.end(), 0); }
    int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        if (rank_[px] < rank_[py]) swap(px, py);
        parent[py] = px;
        if (rank_[px] == rank_[py]) rank_[px]++;
        return true;
    }
};

long long kruskal(int n, vector<tuple<int,int,int>>& edges) {
    sort(edges.begin(), edges.end());
    UnionFind uf(n);
    long long mstWeight = 0;
    int edgeCount = 0;
    for (auto [w, u, v] : edges) {
        if (uf.unite(u, v)) {
            mstWeight += w;
            if (++edgeCount == n - 1) break;
        }
    }
    return mstWeight;
}

// Time: O((V + E) log V), Space: O(V)
long long prim(vector<vector<pair<int,int>>>& adj) {
    int n = adj.size();
    vector<bool> inMST(n, false);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, 0});
    long long mstWeight = 0;
    int count = 0;
    while (!pq.empty() && count < n) {
        auto [w, u] = pq.top(); pq.pop();
        if (inMST[u]) continue;
        inMST[u] = true;
        mstWeight += w;
        count++;
        for (auto [v, wt] : adj[u])
            if (!inMST[v]) pq.push({wt, v});
    }
    return mstWeight;
}

// Time: O(V + E). If order.size() < n, graph has a cycle.
vector<int> topologicalSort(int n, vector<vector<int>>& adj) {
    vector<int> indegree(n, 0);
    for (int u = 0; u < n; u++)
        for (int v : adj[u]) indegree[v]++;
    queue<int> q;
    for (int i = 0; i < n; i++)
        if (indegree[i] == 0) q.push(i);
    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u])
            if (--indegree[v] == 0) q.push(v);
    }
    return order;
}

// Reverse post-order. Time: O(V + E)
vector<int> topoSortDFS(int n, vector<vector<int>>& adj) {
    vector<int> order, state(n, 0);
    bool hasCycle = false;
    function<void(int)> dfs = [&](int u) {
        if (hasCycle) return;
        state[u] = 1;
        for (int v : adj[u]) {
            if (state[v] == 1) { hasCycle = true; return; }
            if (state[v] == 0) dfs(v);
        }
        state[u] = 2;
        order.push_back(u);
    };
    for (int i = 0; i < n; i++) if (state[i] == 0) dfs(i);
    reverse(order.begin(), order.end());
    return order;
}

// Time: O(V + E)
bool hasCycleDirected(int n, vector<vector<int>>& adj) {
    vector<int> color(n, 0);
    function<bool(int)> dfs = [&](int u) -> bool {
        color[u] = 1;
        for (int v : adj[u]) {
            if (color[v] == 1) return true;
            if (color[v] == 0 && dfs(v)) return true;
        }
        color[u] = 2;
        return false;
    };
    for (int i = 0; i < n; i++)
        if (color[i] == 0 && dfs(i)) return true;
    return false;
}

// Time: O(E * alpha(V))
bool hasCycleUndirected(int n, vector<pair<int,int>>& edges) {
    UnionFind uf(n);
    for (auto [u, v] : edges)
        if (uf.find(u) == uf.find(v)) return true;
        else uf.unite(u, v);
    return false;
}

// Time: O(V + E)
vector<vector<int>> kosaraju(int n, vector<vector<int>>& adj) {
    vector<bool> visited(n, false);
    vector<int> order;
    function<void(int)> dfs1 = [&](int u) {
        visited[u] = true;
        for (int v : adj[u]) if (!visited[v]) dfs1(v);
        order.push_back(u);
    };
    for (int i = 0; i < n; i++) if (!visited[i]) dfs1(i);

    vector<vector<int>> radj(n);
    for (int u = 0; u < n; u++)
        for (int v : adj[u]) radj[v].push_back(u);

    fill(visited.begin(), visited.end(), false);
    vector<vector<int>> sccs;
    function<void(int, vector<int>&)> dfs2 = [&](int u, vector<int>& comp) {
        visited[u] = true;
        comp.push_back(u);
        for (int v : radj[u]) if (!visited[v]) dfs2(v, comp);
    };
    for (int i = n - 1; i >= 0; i--) {
        int u = order[i];
        if (!visited[u]) { sccs.push_back({}); dfs2(u, sccs.back()); }
    }
    return sccs;
}