Strongly Connected Components

A strongly connected component in a directed graph is a maximal subgraph where every pair of vertices can reach eachother. To find SCCs, Tarjan's algorithm uses depth-first search (DFS) and maintains two key arrays: disc (discovery time) and low (lowest discovery time reachable from the current vertex).

The algorithm works as follows:

1. Perform DFS from any unvisited vertex, assigning discovery times.
2. For each vertex u, update low[u] based on its neighbors.
3. If a neighbor v is unvisited, recursively process it.
4. If v is on the DFS stack, update low[u] = min(low[u], disc[v]).
5. If low[u] == disc[u], u is the root of an SCC. Pop vertices from the stack until u.

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

vector<int> adj[10001];
int disc[10001], low[10001], onStack[10001];
stack<int> st;
int timer, sccCount;

void tarjan(int node) {
    disc[node] = low[node] = ++timer;
    st.push(node);
    onStack[node] = 1;
    
    for (int neighbor : adj[node]) {
        if (!disc[neighbor]) {
            tarjan(neighbor);
            low[node] = min(low[node], low[neighbor]);
        } else if (onStack[neighbor]) {
            low[node] = min(low[node], disc[neighbor]);
        }
    }
    
    if (low[node] == disc[node]) {
        sccCount++;
        while (st.top() != node) {
            onStack[st.top()] = 0;
            st.pop();
        }
        onStack[node] = 0;
        st.pop();
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }
    
    for (int i = 1; i <= n; i++) {
        if (!disc[i]) tarjan(i);
    }
    
    cout << sccCount << endl;
    return 0;
}

Graph Contraction

Graph contraction involves collapsing each SCC into a single vertex, creating a directed acyclic graph (DAG). This reduces complexity while preserving important graph properties. After identifying SCCs, we build a new graph where each SCC is a vertex, and edges exist between SCCs if there was an edge between their original vertices.

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

vector<int> adj[10001], contracted[10001];
int disc[10001], low[10001], onStack[10001];
int sccId[10001], sccWeight[10001], nodeWeight[10001];
stack<int> st;
int timer, sccCount, inDegree[10001];
long long dp[10001];

void findSCCs(int node) {
    disc[node] = low[node] = ++timer;
    st.push(node);
    onStack[node] = 1;
    
    for (int neighbor : adj[node]) {
        if (!disc[neighbor]) {
            findSCCs(neighbor);
            low[node] = min(low[node], low[neighbor]);
        } else if (onStack[neighbor]) {
            low[node] = min(low[node], disc[neighbor]);
        }
    }
    
    if (low[node] == disc[node]) {
        int v;
        sccCount++;
        do {
            v = st.top();
            st.pop();
            onStack[v] = 0;
            sccId[v] = sccCount;
            sccWeight[sccCount] += nodeWeight[v];
        } while (v != node);
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> nodeWeight[i];
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }
    
    for (int i = 1; i <= n; i++) {
        if (!disc[i]) findSCCs(i);
    }
    
    for (int u = 1; u <= n; u++) {
        for (int v : adj[u]) {
            if (sccId[u] != sccId[v]) {
                contracted[sccId[u]].push_back(sccId[v]);
                inDegree[sccId[v]]++;
            }
        }
    }
    
    queue<int> q;
    for (int i = 1; i <= sccCount; i++) {
        if (!inDegree[i]) {
            q.push(i);
            dp[i] = sccWeight[i];
        }
    }
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : contracted[u]) {
            dp[v] = max(dp[v], dp[u] + sccWeight[v]);
            if (--inDegree[v] == 0) q.push(v);
        }
    }
    
    long long result = 0;
    for (int i = 1; i <= sccCount; i++) {
        result = max(result, dp[i]);
    }
    cout << result << endl;
    return 0;
}

Articulation Points

An articulation point (or cut vertex) in an undirected graph is a vertex whose removal increases the number of connected components. Using Tarjan's algorithm:

• For non-root vertices: If a vertex u has a child v such that low[v] >= disc[u], then u is an articulation point.
• For the root vertex: If it has two or more children in the DFS tree, it's an articulation point.

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

vector<int> adj[10001];
int disc[10001], low[10001];
set<int> articulationPoints;
int timer;

void findArticulationPoints(int u, int parent) {
    disc[u] = low[u] = ++timer;
    int childCount = 0;
    
    for (int v : adj[u]) {
        if (!disc[v]) {
            childCount++;
            findArticulationPoints(v, u);
            low[u] = min(low[u], low[v]);
            
            if (parent != -1 && low[v] >= disc[u]) {
                articulationPoints.insert(u);
            }
        } else if (v != parent) {
            low[u] = min(low[u], disc[v]);
        }
    }
    
    if (parent == -1 && childCount > 1) {
        articulationPoints.insert(u);
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    for (int i = 1; i <= n; i++) {
        if (!disc[i]) findArticulationPoints(i, -1);
    }
    
    cout << articulationPoints.size() << endl;
    for (int point : articulationPoints) {
        cout << point << " ";
    }
    return 0;
}

Bridges

A bridge (or cut edge) in an undirected graph is an edge whose removal increases the number of connected components. An edge (u, v) is a bridge if low[v] > disc[u], where v is a child of u in the DFS tree.

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

vector<int> adj[10001];
int disc[10001], low[10001];
vector<pair<int, int>> bridges;
int timer;

void findBridges(int u, int parent) {
    disc[u] = low[u] = ++timer;
    
    for (int v : adj[u]) {
        if (!disc[v]) {
            findBridges(v, u);
            low[u] = min(low[u], low[v]);
            
            if (low[v] > disc[u]) {
                bridges.push_back({min(u, v), max(u, v)});
            }
        } else if (v != parent) {
            low[u] = min(low[u], disc[v]);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    for (int i = 1; i <= n; i++) {
        if (!disc[i]) findBridges(i, -1);
    }
    
    sort(bridges.begin(), bridges.end());
    for (auto& bridge : bridges) {
        cout << bridge.first << " " << bridge.second << endl;
    }
    return 0;
}