Advanced Graph Theory

Advanced graph theory algorithms including bipartite matching, Eulerian circuits, strongly connected components, and biconnected components. These algorithms are essential for solving complex graph problems in competitive programming.

Bipartite Graphs and Matching

A bipartite graph can be divided into two disjoint sets where edges only connect vertices from different sets.

Bipartite Graph Detection and Maximum Matching

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class BipartiteChecker {
private:
    vector<vector<int>> graph;
    vector<int> color;
    int n;
    
public:
    BipartiteChecker(int vertices) : n(vertices) {
        graph.resize(n);
        color.assign(n, -1);
    }
    
    void addEdge(int u, int v) {
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    bool isBipartite() {
        for (int start = 0; start < n; start++) {
            if (color[start] == -1) {
                queue<int> q;
                q.push(start);
                color[start] = 0;
                
                while (!q.empty()) {
                    int u = q.front();
                    q.pop();
                    
                    for (int v : graph[u]) {
                        if (color[v] == -1) {
                            color[v] = 1 - color[u];
                            q.push(v);
                        } else if (color[v] == color[u]) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
};

int main() {
    BipartiteChecker checker(6);
    
    checker.addEdge(0, 3);
    checker.addEdge(0, 4);
    checker.addEdge(1, 3);
    checker.addEdge(1, 5);
    checker.addEdge(2, 4);
    checker.addEdge(2, 5);
    
    if (checker.isBipartite()) {
        cout << "Graph is bipartite!" << endl;
    } else {
        cout << "Graph is not bipartite!" << endl;
    }
    
    return 0;
}

Uses BFS coloring to check if vertices can be divided into two sets with no edges within sets.

Strongly Connected Components (SCC)

A strongly connected component is a maximal set of vertices such that there is a path from each vertex to every other vertex in the component.

Tarjan's Algorithm for Strongly Connected Components

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

class TarjanSCC {
private:
    vector<vector<int>> graph;
    vector<int> dfn, low, sccId;
    vector<bool> inStack;
    stack<int> st;
    int timer, sccCount;
    
    void tarjan(int u) {
        dfn[u] = low[u] = ++timer;
        st.push(u);
        inStack[u] = true;
        
        for (int v : graph[u]) {
            if (dfn[v] == 0) {
                // Unvisited vertex
                tarjan(v);
                low[u] = min(low[u], low[v]);
            } else if (inStack[v]) {
                // Back edge to vertex in current SCC
                low[u] = min(low[u], dfn[v]);
            }
        }
        
        // If u is root of SCC
        if (dfn[u] == low[u]) {
            int v;
            do {
                v = st.top();
                st.pop();
                inStack[v] = false;
                sccId[v] = sccCount;
            } while (v != u);
            sccCount++;
        }
    }
    
public:
    TarjanSCC(int n) : graph(n), dfn(n, 0), low(n, 0), 
                       sccId(n, -1), inStack(n, false), 
                       timer(0), sccCount(0) {}
    
    void addEdge(int u, int v) {
        graph[u].push_back(v);
    }
    
    void findSCC() {
        for (int i = 0; i < graph.size(); i++) {
            if (dfn[i] == 0) {
                tarjan(i);
            }
        }
    }
    
    int getSCCCount() { return sccCount; }
    
    vector<int> getSCCIds() { return sccId; }
    
    // Build condensation graph
    vector<vector<int>> buildCondensationGraph() {
        vector<vector<int>> condensed(sccCount);
        vector<set<int>> edges(sccCount);
        
        for (int u = 0; u < graph.size(); u++) {
            for (int v : graph[u]) {
                if (sccId[u] != sccId[v]) {
                    edges[sccId[u]].insert(sccId[v]);
                }
            }
        }
        
        for (int i = 0; i < sccCount; i++) {
            for (int v : edges[i]) {
                condensed[i].push_back(v);
            }
        }
        
        return condensed;
    }
};

int main() {
    cout << "Testing Tarjan's SCC Algorithm:" << endl;
    
    TarjanSCC tarjan(8);
    
    // Build a directed graph with SCCs
    tarjan.addEdge(0, 1);
    tarjan.addEdge(1, 2);
    tarjan.addEdge(2, 0);  // SCC: {0, 1, 2}
    tarjan.addEdge(2, 3);
    tarjan.addEdge(3, 4);
    tarjan.addEdge(4, 5);
    tarjan.addEdge(5, 3);  // SCC: {3, 4, 5}
    tarjan.addEdge(5, 6);
    tarjan.addEdge(6, 7);  // SCC: {6}, {7}
    
    tarjan.findSCC();
    
    cout << "Number of SCCs: " << tarjan.getSCCCount() << endl;
    
    vector<int> sccIds = tarjan.getSCCIds();
    cout << "SCC assignments:" << endl;
    for (int i = 0; i < sccIds.size(); i++) {
        cout << "Vertex " << i << " -> SCC " << sccIds[i] << endl;
    }
    
    auto condensed = tarjan.buildCondensationGraph();
    cout << "\nCondensation graph edges:" << endl;
    for (int i = 0; i < condensed.size(); i++) {
        cout << "SCC " << i << " -> ";
        for (int v : condensed[i]) {
            cout << "SCC " << v << " ";
        }
        cout << endl;
    }
    
    return 0;
}

Tarjan's algorithm uses DFS with timestamps to find strongly connected components in O(V+E) time. It maintains a stack of vertices and uses low-link values to identify SCC roots.

Eulerian Graphs and Circuits

An Eulerian circuit is a closed walk that visits every edge exactly once. A graph has an Eulerian circuit if and only if every vertex has even degree.

Hierholzer's Algorithm for Eulerian Circuit

#include <iostream>
#include <vector>
#include <stack>
#include <list>
using namespace std;

class EulerianCircuit {
private:
    vector<list<int>> graph;
    int n;
    
public:
    EulerianCircuit(int vertices) : n(vertices), graph(vertices) {}
    
    void addEdge(int u, int v) {
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    bool hasEulerianCircuit() {
        // Check if all vertices have even degree
        for (int i = 0; i < n; i++) {
            if (graph[i].size() % 2 != 0) {
                return false;
            }
        }
        return true;
    }
    
    vector<int> findEulerianCircuit() {
        if (!hasEulerianCircuit()) {
            return {};
        }
        
        vector<int> circuit;
        stack<int> currPath;
        
        // Start from vertex 0
        currPath.push(0);
        
        while (!currPath.empty()) {
            int curr = currPath.top();
            
            if (!graph[curr].empty()) {
                // Take next edge
                int next = graph[curr].front();
                graph[curr].pop_front();
                
                // Remove reverse edge
                graph[next].remove(curr);
                
                currPath.push(next);
            } else {
                // No more edges, add to circuit
                circuit.push_back(curr);
                currPath.pop();
            }
        }
        
        return circuit;
    }
    
    void printCircuit(const vector<int>& circuit) {
        if (circuit.empty()) {
            cout << "No Eulerian circuit exists!" << endl;
            return;
        }
        
        cout << "Eulerian Circuit: ";
        for (int i = circuit.size() - 1; i >= 0; i--) {
            cout << circuit[i];
            if (i > 0) cout << " -> ";
        }
        cout << endl;
    }
};

int main() {
    cout << "Testing Hierholzer's Eulerian Circuit Algorithm:" << endl;
    
    // Create a graph with Eulerian circuit
    EulerianCircuit ec(5);
    
    // Build a cycle graph: 0-1-2-3-4-0 with additional edges
    ec.addEdge(0, 1);
    ec.addEdge(1, 2);
    ec.addEdge(2, 3);
    ec.addEdge(3, 4);
    ec.addEdge(4, 0);
    ec.addEdge(0, 2);  // Additional edge to make degrees even
    
    if (ec.hasEulerianCircuit()) {
        cout << "Graph has Eulerian circuit!" << endl;
        vector<int> circuit = ec.findEulerianCircuit();
        ec.printCircuit(circuit);
    } else {
        cout << "Graph does not have Eulerian circuit!" << endl;
    }
    
    return 0;
}

Hierholzer's algorithm finds Eulerian circuits by building a path and merging cycles. It works by following edges until no more are available, then backtracking to find additional cycles.