Adjacency List Implementation (Static Forward Star)

Graphs can be efficiently represented using a static array-based linked structure. This approach avoids dynamic memory allocation overhead and provides fast edge traversal.

struct GraphEdge {
    int weight;
    int target;
    int nextEdge;
} edges[MAX_E];
int head[MAX_V];
int edgeCount = 0;

inline void addEdge(int u, int v, int w) {
    edges[++edgeCount] = {w, v, head[u]};
    head[u] = edgeCount;
}

// Traversal example
void processOutEdges(int u) {
    for (int e = head[u]; e != 0; e = edges[e].nextEdge) {
        int v = edges[e].target;
        int w = edges[e].weight;
        // Process edge (u, v) with weight w
    }
}

Tree Centroid Detection

A tree centroid is a node that minimizes the maximum size of the resulting subtrees when removed. The algorithm computes subtree sizes via DFS and tracks the optimal balance.

int subtreeSize[MAX_V], centroidBalance = INT_MAX;

void computeCentroid(int u, int parentNode) {
    subtreeSize[u] = 1;
    int maxBranch = 0;
    for (int e = head[u]; e; e = edges[e].nextEdge) {
        int v = edges[e].target;
        if (v == parentNode) continue;
        computeCentroid(v, u);
        subtreeSize[u] += subtreeSize[v];
        maxBranch = max(maxBranch, subtreeSize[v]);
    }
    maxBranch = max(maxBranch, totalVertices - subtreeSize[u]);
    centroidBalance = min(centroidBalance, maxBranch);
}

Tree Diameter Calculation

The diameter is found by performing two depth-first searches. The first DFS locates the farthest node from an arbitrary starting point, and the second DFS finds the maximum distance from that node.

bool visitedD[MAX_V];

void dfsDistance(int u, int currentNode, int distArray[]) {
    visitedD[u] = true;
    for (int e = head[u]; e; e = edges[e].nextEdge) {
        int v = edges[e].target;
        int w = edges[e].weight;
        if (!visitedD[v]) {
            distArray[v] = distArray[u] + w;
            dfsDistance(v, currentNode, distArray);
        }
    }
}

// Main execution flow
memset(visitedD, 0, sizeof(visitedD));
dfsDistance(startNode, 1, distFirst);
int endpointA = 1;
for (int i = 2; i <= n; ++i) 
    if (distFirst[i] > distFirst[endpointA]) endpointA = i;

memset(visitedD, 0, sizeof(visitedD));
dfsDistance(endpointA, 1, distSecond);
int diameter = 0;
for (int i = 1; i <= n; ++i) 
    diameter = max(diameter, distSecond[i]);
printf("%d\n", diameter);

Topological Sorting

Kahn's algorithm processes nodes with zero in-degree using a queue, decrementing neighbor counts as each node is extracted. It produces a valid linear ordering for DAGs.

int inDegree[MAX_V], topoResult[MAX_V], topoPtr = 0;
queue<int> processQueue;

void executeTopoSort() {
    for (int i = 1; i <= n; ++i)
        if (inDegree[i] == 0) processQueue.push(i);
    
    while (!processQueue.empty()) {
        int u = processQueue.front();
        processQueue.pop();
        topoResult[++topoPtr] = u;
        
        for (int e = head[u]; e; e = edges[e].nextEdge) {
            int v = edges[e].target;
            inDegree[v]--;
            if (inDegree[v] == 0) processQueue.push(v);
        }
    }
}</int>

Lowest Common Ancestor (Binary Lifting)

Preprocessing ancestors in powers of two allows logarithmic-time queries. Depth normalization is required before lifting nodes to the same level.

int depth[MAX_V], ancestor[MAX_V][20];

void dfsLCASetup(int u, int p) {
    for (int e = head[u]; e; e = edges[e].nextEdge) {
        int v = edges[e].target;
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        ancestor[v][0] = u;
        dfsLCASetup(v, u);
    }
}

void buildLCA() {
    for (int j = 1; j < 20; ++j)
        for (int i = 1; i <= n; ++i)
            ancestor[i][j] = ancestor[ancestor[i][j-1]][j-1];
}

int queryLCA(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    for (int j = 19; j >= 0; --j)
        if (depth[ancestor[u][j]] >= depth[v]) 
            u = ancestor[u][j];
    if (u == v) return u;
    for (int j = 19; j >= 0; --j)
        if (ancestor[u][j] != ancestor[v][j]) {
            u = ancestor[u][j];
            v = ancestor[v][j];
        }
    return ancestor[u][0];
}

Shortest Path Algorithms

SPFA with Negative Cycle Detection

Single-source shortest paths can be found using a queue-based relaxation. Tracking path length helps identify negative cycles when it exceeds the vertex count.

int distance[MAX_V], pathSteps[MAX_V];
bool inQueue[MAX_V];
queue<int> q;

bool detectNegativeCycle(int src) {
    memset(distance, 0x3f, sizeof(distance));
    memset(pathSteps, 0, sizeof(pathSteps));
    distance[src] = 0;
    q.push(src); inQueue[src] = true;
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        inQueue[u] = false;
        for (int e = head[u]; e; e = edges[e].nextEdge) {
            int v = edges[e].target;
            int w = edges[e].weight;
            if (distance[u] + w < distance[v]) {
                distance[v] = distance[u] + w;
                pathSteps[v] = pathSteps[u] + 1;
                if (pathSteps[v] >= n) return true;
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                }
            }
        }
    }
    return false;
}</int>

Heap-Optimized Dijkstra

Non-negative edge weights are handled efficiently by extracting the minimum tentative distance node from a priority queue.

typedef pair<long int="" long=""> NodeDist;
priority_queue<nodedist vector="">, greater<nodedist>> minHeap;
long long distHeap[MAX_V];
bool finalized[MAX_V];

void runDijkstra(int start) {
    fill(distHeap, distHeap + MAX_V, LLONG_MAX);
    distHeap[start] = 0;
    minHeap.push({0, start});
    
    while (!minHeap.empty()) {
        int u = minHeap.top().second;
        minHeap.pop();
        if (finalized[u]) continue;
        finalized[u] = true;
        
        for (int e = head[u]; e; e = edges[e].nextEdge) {
            int v = edges[e].target;
            int w = edges[e].weight;
            if (distHeap[u] + w < distHeap[v]) {
                distHeap[v] = distHeap[u] + w;
                if (!finalized[v]) minHeap.push({distHeap[v], v});
            }
        }
    }
}</nodedist></nodedist></long>

Floyd-Warshall and Transitive Closure

All-pairs shortest paths and reachability matrices are computed using dynamic programming over intermediate vertices.

int adjMatrix[MAX_V][MAX_V];

void floydWarshall() {
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                adjMatrix[i][j] = min(adjMatrix[i][j], adjMatrix[i][k] + adjMatrix[k][j]);
}

void transitiveClosure() {
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                adjMatrix[i][j] |= adjMatrix[i][k] & adjMatrix[k][j];
}

Minimum Spanning Tree: Kruskal's Algorithm

Edges are sorted by weight and processed sequentially. Disjoint Set Union (DSU) structures track connected components to prevent cycles.

struct RawEdge { int u, v, w; } rawEdges[MAX_E];
int parentDSU[MAX_V];

int findSet(int x) {
    return parentDSU[x] == x ? x : parentDSU[x] = findSet(parentDSU[x]);
}

void uniteSets(int x, int y) {
    x = findSet(x), y = findSet(y);
    if (x != y) parentDSU[x] = y;
}

void buildMST() {
    for (int i = 1; i <= n; ++i) parentDSU[i] = i;
    sort(rawEdges + 1, rawEdges + m + 1, [](const RawEdge& a, const RawEdge& b) {
        return a.w < b.w;
    });
    
    long long mstCost = 0;
    for (int i = 1; i <= m; ++i) {
        if (findSet(rawEdges[i].u) == findSet(rawEdges[i].v)) continue;
        uniteSets(rawEdges[i].u, rawEdges[i].v);
        mstCost += rawEdges[i].w;
    }
}

Tarjan's Algorithm Variants

Strongly Connected Components (Directed Graph)

int discTime[MAX_V], lowLink[MAX_V], timerVal = 0;
int stackArr[MAX_V], stackTop = 0;
bool onStack[MAX_V];
int sccId[MAX_V], sccCount = 0;

void tarjanSCC(int u) {
    discTime[u] = lowLink[u] = ++timerVal;
    stackArr[++stackTop] = u;
    onStack[u] = true;
    
    for (int e = head[u]; e; e = edges[e].nextEdge) {
        int v = edges[e].target;
        if (!discTime[v]) {
            tarjanSCC(v);
            lowLink[u] = min(lowLink[u], lowLink[v]);
        } else if (onStack[v]) {
            lowLink[u] = min(lowLink[u], discTime[v]);
        }
    }
    
    if (lowLink[u] == discTime[u]) {
        sccCount++;
        int popped;
        do {
            popped = stackArr[stackTop--];
            onStack[popped] = false;
            sccId[popped] = sccCount;
        } while (popped != u);
    }
}

Articulation Points and Vertex Biconnected Components

int dfsNum[MAX_V], lowVal[MAX_V], visitTime = 0;
int stk[MAX_V], stkPtr = 0;
bool isArticulation[MAX_V];
vector<int> vertexBCC[MAX_V];
int bccCount = 0;

void tarjanArticulation(int u, int root) {
    dfsNum[u] = lowVal[u] = ++visitTime;
    stk[++stkPtr] = u;
    bool hasChild = false;
    
    for (int e = head[u]; e; e = edges[e].nextEdge) {
        int v = edges[e].target;
        if (!dfsNum[v]) {
            hasChild = true;
            tarjanArticulation(v, root);
            lowVal[u] = min(lowVal[u], lowVal[v]);
            if (lowVal[v] >= dfsNum[u]) {
                if (u != root || hasChild) isArticulation[u] = true;
                bccCount++;
                int popped;
                do {
                    popped = stk[stkPtr--];
                    vertexBCC[bccCount].push_back(popped);
                } while (popped != v);
                vertexBCC[bccCount].push_back(u);
            }
        } else {
            lowVal[u] = min(lowVal[u], dfsNum[v]);
        }
    }
}</int>

Bridges and Edge Biconnected Components

int disc[MAX_V], low[MAX_V], timeCounter = 0;
bool isBridge[MAX_E];

inline int getReverseEdge(int id) { return (id & 1) ? id + 1 : id - 1; }

void findBridges(int u, int parentEdge) {
    disc[u] = low[u] = ++timeCounter;
    for (int e = head[u]; e; e = edges[e].nextEdge) {
        int v = edges[e].target;
        if (!disc[v]) {
            findBridges(v, e);
            low[u] = min(low[u], low[v]);
            if (low[v] > disc[u]) {
                isBridge[e] = isBridge[getReverseEdge(e)] = true;
            }
        } else if (e != getReverseEdge(parentEdge)) {
            low[u] = min(low[u], disc[v]);
        }
    }
}

int compId[MAX_V], compCount = 0;
vector<int> edgeBCC[MAX_V];

void colorComponent(int u) {
    edgeBCC[compId[u]].push_back(u);
    for (int e = head[u]; e; e = edges[e].nextEdge) {
        if (isBridge[e]) continue;
        int v = edges[e].target;
        if (!compId[v]) {
            compId[v] = compId[u];
            colorComponent(v);
        }
    }
}</int>

Block-Cut Tree Construction

int discovery[MAX_V], minLow[MAX_V], clockTick = 0;
int treeStack[MAX_V], treeTop = 0;
int virtualNodeIdx = 0;
Graph tree; // Adjacency list for the new tree

void buildBlockCutTree(int u) {
    discovery[u] = minLow[u] = ++clockTick;
    treeStack[++treeTop] = u;
    
    for (int e = head[u]; e; e = edges[e].nextEdge) {
        int v = edges[e].target;
        if (discovery[v]) {
            minLow[u] = min(minLow[u], discovery[v]);
        } else {
            buildBlockCutTree(v);
            minLow[u] = min(minLow[u], minLow[v]);
            if (minLow[v] == discovery[u]) {
                virtualNodeIdx++;
                int curr = 0;
                while (curr != v) {
                    curr = treeStack[treeTop--];
                    tree.addEdge(virtualNodeIdx, curr);
                    tree.addEdge(curr, virtualNodeIdx);
                }
                tree.addEdge(u, virtualNodeIdx);
                tree.addEdge(virtualNodeIdx, u);
            }
        }
    }
}

Bipartite Matching: Hungarian Algorithm

Maximum matching in bipartite graphs is found via augmenting path searches using DFS and a visitation array to prevent cycles during a single search phase.

int matchRight[MAX_V];
bool visitedPhase[MAX_V];

bool findAugmentingPath(int u) {
    for (int e = head[u]; e; e = edges[e].nextEdge) {
        int v = edges[e].target;
        if (visitedPhase[v]) continue;
        visitedPhase[v] = true;
        if (matchRight[v] == 0 || findAugmentingPath(matchRight[v])) {
            matchRight[v] = u;
            return true;
        }
    }
    return false;
}