owlingcode

Directed Graph Fundamentals

Directed graphs (digraphs) have edges with direction, creating unique properties and algorithms different from undirected graphs. Understanding topological ordering and strong connectivity is crucial.

Basic Operations

// Directed graph representation
vector<vector<int>> adj; // Adjacency list
vector<int> indegree, outdegree;

void addDirectedEdge(int u, int v) {
    adj[u].push_back(v);
    outdegree[u]++;
    indegree[v]++;
}

// Check if edge exists
bool hasEdge(int u, int v) {
    return find(adj[u].begin(), adj[u].end(), v) != adj[u].end();
}
                    

Topological Sorting

Topological sorting produces a linear ordering of vertices where for every directed edge u→v, u appears before v in the ordering. Only possible for DAGs.

Kahn's Algorithm (BFS-based)

// Kahn's algorithm for topological sorting
vector<int> topologicalSortKahn(int n, vector<vector<int>>& adj) {
    vector<int> indegree(n, 0);
    
    // Calculate indegrees
    for(int u = 0; u < n; u++) {
        for(int v : adj[u]) {
            indegree[v]++;
        }
    }
    
    queue<int> q;
    
    // Add vertices with indegree 0
    for(int i = 0; i < n; i++) {
        if(indegree[i] == 0) {
            q.push(i);
        }
    }
    
    vector<int> topoOrder;
    
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        topoOrder.push_back(u);
        
        // Remove u and decrease indegree of neighbors
        for(int v : adj[u]) {
            indegree[v]--;
            if(indegree[v] == 0) {
                q.push(v);
            }
        }
    }
    
    // Check if topological sort is possible (no cycles)
    if(topoOrder.size() != n) {
        return {}; // Cycle detected
    }
    
    return topoOrder;
}
                    

DFS-based Topological Sort

vector<int> topoOrder;
vector<int> color; // 0: white, 1: gray, 2: black
bool hasCycle = false;

void topoDFS(int u, vector<vector<int>>& adj) {
    color[u] = 1; // Mark as gray (visiting)
    
    for(int v : adj[u]) {
        if(color[v] == 1) {
            hasCycle = true; // Back edge found (cycle)
            return;
        }
        if(color[v] == 0) {
            topoDFS(v, adj);
        }
    }
    
    color[u] = 2; // Mark as black (finished)
    topoOrder.push_back(u);
}

vector<int> topologicalSortDFS(int n, vector<vector<int>>& adj) {
    color.assign(n, 0);
    topoOrder.clear();
    hasCycle = false;
    
    for(int i = 0; i < n; i++) {
        if(color[i] == 0) {
            topoDFS(i, adj);
            if(hasCycle) return {}; // Cycle detected
        }
    }
    
    reverse(topoOrder.begin(), topoOrder.end());
    return topoOrder;
}
                    

Strongly Connected Components

A strongly connected component is a maximal set of vertices where every vertex is reachable from every other vertex in the same component.

Kosaraju's Algorithm

class StronglyConnectedComponents {
private:
    int n;
    vector<vector<int>> adj, radj; // Original and reverse graph
    vector<bool> visited;
    vector<int> order, component;
    int numComponents;
    
    void dfs1(int u) {
        visited[u] = true;
        for(int v : adj[u]) {
            if(!visited[v]) {
                dfs1(v);
            }
        }
        order.push_back(u);
    }
    
    void dfs2(int u, int comp) {
        component[u] = comp;
        for(int v : radj[u]) {
            if(component[v] == -1) {
                dfs2(v, comp);
            }
        }
    }
    
public:
    StronglyConnectedComponents(int n) : n(n), adj(n), radj(n) {}
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        radj[v].push_back(u); // Reverse edge
    }
    
    void findSCCs() {
        // Step 1: Get finishing order using DFS on original graph
        visited.assign(n, false);
        order.clear();
        
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                dfs1(i);
            }
        }
        
        // Step 2: DFS on reverse graph in reverse finishing order
        component.assign(n, -1);
        numComponents = 0;
        
        reverse(order.begin(), order.end());
        
        for(int u : order) {
            if(component[u] == -1) {
                dfs2(u, numComponents++);
            }
        }
    }
    
    int getComponent(int u) { return component[u]; }
    int getNumComponents() { return numComponents; }
    
    vector<vector<int>> getComponentGroups() {
        vector<vector<int>> groups(numComponents);
        for(int i = 0; i < n; i++) {
            groups[component[i]].push_back(i);
        }
        return groups;
    }
    
    // Build condensation graph (DAG of SCCs)
    vector<vector<int>> getCondensationGraph() {
        vector<vector<int>> condAdj(numComponents);
        set<pair<int, int>> edges;
        
        for(int u = 0; u < n; u++) {
            for(int v : adj[u]) {
                int compU = component[u], compV = component[v];
                if(compU != compV && edges.find({compU, compV}) == edges.end()) {
                    condAdj[compU].push_back(compV);
                    edges.insert({compU, compV});
                }
            }
        }
        
        return condAdj;
    }
};
                    

Tarjan's Algorithm (Alternative)

class TarjanSCC {
private:
    int n, timer, sccCount;
    vector<vector<int>> adj;
    vector<int> low, disc, sccId;
    vector<bool> onStack;
    stack<int> st;
    
    void tarjanDFS(int u) {
        low[u] = disc[u] = timer++;
        st.push(u);
        onStack[u] = true;
        
        for(int v : adj[u]) {
            if(disc[v] == -1) {
                tarjanDFS(v);
                low[u] = min(low[u], low[v]);
            } else if(onStack[v]) {
                low[u] = min(low[u], disc[v]);
            }
        }
        
        // Root of SCC
        if(low[u] == disc[u]) {
            while(true) {
                int v = st.top();
                st.pop();
                onStack[v] = false;
                sccId[v] = sccCount;
                if(v == u) break;
            }
            sccCount++;
        }
    }
    
public:
    TarjanSCC(int n, vector<vector<int>>& graph) : n(n), adj(graph), timer(0), sccCount(0) {
        low.assign(n, -1);
        disc.assign(n, -1);
        sccId.assign(n, -1);
        onStack.assign(n, false);
        
        for(int i = 0; i < n; i++) {
            if(disc[i] == -1) {
                tarjanDFS(i);
            }
        }
    }
    
    int getComponentId(int u) { return sccId[u]; }
    int getNumComponents() { return sccCount; }
};
                    

Dynamic Programming on DAGs

DAGs enable efficient DP solutions since we can process vertices in topological order:

Longest Path in DAG

// Longest path in weighted DAG
vector<long long> longestPathDAG(int n, vector<vector<pair<int, int>>>& adj) {
    vector<int> topoOrder = topologicalSortKahn(n, convertToUnweighted(adj));
    if(topoOrder.empty()) return {}; // Not a DAG
    
    vector<long long> dist(n, LLONG_MIN);
    dist[topoOrder[0]] = 0; // Start from first vertex in topo order
    
    for(int u : topoOrder) {
        if(dist[u] == LLONG_MIN) continue;
        
        for(auto& edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;
            dist[v] = max(dist[v], dist[u] + weight);
        }
    }
    
    return dist;
}

// Count number of paths in DAG
vector<long long> countPathsDAG(int n, vector<vector<int>>& adj, int source) {
    vector<int> topoOrder = topologicalSortDFS(n, adj);
    if(topoOrder.empty()) return {}; // Not a DAG
    
    vector<long long> pathCount(n, 0);
    pathCount[source] = 1;
    
    for(int u : topoOrder) {
        for(int v : adj[u]) {
            pathCount[v] += pathCount[u];
        }
    }
    
    return pathCount;
}

// DP on DAG: Maximum sum path
long long maxSumPathDAG(int n, vector<vector<int>>& adj, vector<int>& values) {
    vector<int> topoOrder = topologicalSortDFS(n, adj);
    if(topoOrder.empty()) return LLONG_MIN; // Not a DAG
    
    vector<long long> dp(n, LLONG_MIN);
    
    // Initialize all vertices (they can be starting points)
    for(int i = 0; i < n; i++) {
        dp[i] = values[i];
    }
    
    long long maxSum = *max_element(values.begin(), values.end());
    
    for(int u : topoOrder) {
        if(dp[u] == LLONG_MIN) continue;
        
        for(int v : adj[u]) {
            dp[v] = max(dp[v], dp[u] + values[v]);
            maxSum = max(maxSum, dp[v]);
        }
    }
    
    return maxSum;
}
                    

Cycle Detection

Detecting cycles in directed graphs using DFS color coding:

// Cycle detection using DFS colors
bool hasCycleDirected(int n, vector<vector<int>>& adj) {
    vector<int> color(n, 0); // 0: white, 1: gray, 2: black
    
    function<bool(int)> dfs = [&](int u) -> bool {
        color[u] = 1; // Mark as gray
        
        for(int v : adj[u]) {
            if(color[v] == 1) return true; // Back edge (cycle)
            if(color[v] == 0 && dfs(v)) return true;
        }
        
        color[u] = 2; // Mark as black
        return false;
    };
    
    for(int i = 0; i < n; i++) {
        if(color[i] == 0 && dfs(i)) {
            return true;
        }
    }
    
    return false;
}

// Find all vertices in cycles
vector<bool> findVerticesInCycles(int n, vector<vector<int>>>& adj) {
    vector<int> color(n, 0);
    vector<bool> inCycle(n, false);
    vector<int> parent(n, -1);
    
    function<void(int, int)> dfs = [&](int u, int cycleStart) {
        color[u] = 1;
        
        for(int v : adj[u]) {
            if(color[v] == 1) {
                // Found cycle, mark all vertices from v to u
                int curr = u;
                while(curr != v) {
                    inCycle[curr] = true;
                    curr = parent[curr];
                }
                inCycle[v] = true;
            } else if(color[v] == 0) {
                parent[v] = u;
                dfs(v, cycleStart);
            }
        }
        
        color[u] = 2;
    };
    
    for(int i = 0; i < n; i++) {
        if(color[i] == 0) {
            dfs(i, -1);
        }
    }
    
    return inCycle;
}