Graph Connectivity Concepts

A connected component in an undirected graph is a maximal subgraph where every pair of vertices is connected via a path. For directed graphs, a strongly connected component (SCC) is a maximal subgraph where every pair of vertices is mutually reachable via directed paths. SCCs are unique to directed graphs.

In DFS tree analysis, edge types include:

• Tree edges: Parent-child relationships in the DFS tree
• Back edges: Connections from descendants to ancestors
• Forward edges: Connections from ancestors to non-immediate descendants
• Cross edges: Connections between non-ancestor-related vertices

Tarjan's SCC Algorithm

Tarjan's algorithm identifies SCCs in linear time O(V + E) using DFS with stack management. Key concepts:

• dfn[u]: DFS discovery timestamp of vertex u
• low[u]: Smallest timestamp reachable from u's DFS subtree with out using parent edges

Algorithm steps:

1. Initialize timestamps and stack
2. Recursively process neighbors:
   • For unvisited neighbors: recurse and update low[u]
   • For visited neighbors in stack: update low[u] using dfn[v]
3. When low[u] == dfn[u], pop stack to form an SCC

Implementation Example

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

const int MAX_NODES = 5005;
const int MAX_EDGES = 100005;

struct Edge {
  int dest, next;
};

Edge links[MAX_EDGES];
int head[MAX_NODES], timestamp[MAX_NODES], min_reachable[MAX_NODES];
int scc_id[MAX_NODES], scc_size[MAX_NODES];
bool in_stack[MAX_NODES];
stack<int> node_stack;
int edge_count = 0, time_counter = 0, scc_count = 0;

void add_edge(int src, int dest) {
  links[++edge_count] = {dest, head[src]};
  head[src] = edge_count;
}

void find_scc(int u) {
  timestamp[u] = min_reachable[u] = ++time_counter;
  node_stack.push(u);
  in_stack[u] = true;
  
  for (int i = head[u]; i; i = links[i].next) {
    int v = links[i].dest;
    if (!timestamp[v]) {
      find_scc(v);
      min_reachable[u] = min(min_reachable[u], min_reachable[v]);
    } else if (in_stack[v]) {
      min_reachable[u] = min(min_reachable[u], timestamp[v]);
    }
  }

  if (min_reachable[u] == timestamp[u]) {
    scc_count++;
    while (true) {
      int top_node = node_stack.top();
      node_stack.pop();
      in_stack[top_node] = false;
      scc_id[top_node] = scc_count;
      scc_size[scc_count]++;
      if (top_node == u) break;
    }
  }
}

int main() {
  int node_count, edge_count, u, v, dir;
  cin >> node_count >> edge_count;
  
  for (int i = 0; i < edge_count; i++) {
    cin >> u >> v >> dir;
    add_edge(u, v);
    if (dir == 2) add_edge(v, u);
  }

  for (int i = 1; i <= node_count; i++)
    if (!timestamp[i]) find_scc(i);

  int max_scc = *max_element(scc_size + 1, scc_size + scc_count + 1);
  cout << max_scc << endl;
  
  for (int i = 1; i <= node_count; i++)
    if (scc_size[scc_id[i]] == max_scc)
      cout << i << " ";
  
  return 0;
}

Kosaraju's SCC Algorithm

Kosaraju's algorithm uses two DFS passes:

1. First pass: Perform post-order DFS on original graph and push nodes to stack
2. Second pass: Process nodes from stack in reverse order, DFS on transpose graph to identify SCCs

Implementation Example

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

const int MAX_NODES = 10005;

vector<int> graph[MAX_NODES], reversed_graph[MAX_NODES];
int comp_id[MAX_NODES], comp_size[MAX_NODES];
bool visited[MAX_NODES];
stack<int> finish_order;
int comp_count = 0;

void first_dfs(int u) {
  visited[u] = true;
  for (int v : graph[u])
    if (!visited[v]) first_dfs(v);
  finish_order.push(u);
}

void second_dfs(int u, int cid) {
  comp_id[u] = cid;
  comp_size[cid]++;
  for (int v : reversed_graph[u])
    if (!comp_id[v]) second_dfs(v, cid);
}

int main() {
  int node_count, edge_count, u, v;
  cin >> node_count >> edge_count;
  
  for (int i = 0; i < edge_count; i++) {
    cin >> u >> v;
    graph[u].push_back(v);
    reversed_graph[v].push_back(u);
  }

  for (int i = 1; i <= node_count; i++)
    if (!visited[i]) first_dfs(i);
  
  while (!finish_order.empty()) {
    int u = finish_order.top();
    finish_order.pop();
    if (!comp_id[u]) second_dfs(u, ++comp_count);
  }

  for (int c = 1; c <= comp_count; c++) {
    cout << "SCC " < c << ": ";
    for (int i = 1; i <= node_count; i++)
      if (comp_id[i] == c) cout << i << " ";
    cout << endl;
  }
}

Graph Condensation

Condensation creates a DAG by contracting SCCs into single nodes. Implementation steps:

1. Identify SCCs using Tarjan or Kosaraju
2. Create new nodes for each SCC
3. Add edges between SCC nodes when original nodes had inter-component edges

Conednsation Example

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

const int MAX_NODES = 10005;

vector<int> adj[MAX_NODES], condensed_adj[MAX_NODES];
int timestamp[MAX_NODES], min_reachable[MAX_NODES], comp_id[MAX_NODES];
bool in_stack[MAX_NODES];
stack<int> node_stack;
int time_counter = 0, comp_count = 0;

void find_components(int u) {
  timestamp[u] = min_reachable[u] = ++time_counter;
  node_stack.push(u);
  in_stack[u] = true;
  
  for (int v : adj[u]) {
    if (!timestamp[v]) {
      find_components(v);
      min_reachable[u] = min(min_reachable[u], min_reachable[v]);
    } else if (in_stack[v]) {
      min_reachable[u] = min(min_reachable[u], timestamp[v]);
    }
  }

  if (min_reachable[u] == timestamp[u]) {
    comp_count++;
    while (true) {
      int top_node = node_stack.top();
      node_stack.pop();
      in_stack[top_node] = false;
      comp_id[top_node] = comp_count;
      if (top_node == u) break;
    }
  }
}

void build_condensed_graph(int n) {
  for (int u = 1; u <= n; u++) {
    for (int v : adj[u]) {
      if (comp_id[u] != comp_id[v]) {
        condensed_adj[comp_id[u]].push_back(comp_id[v]);
      }
    }
  }
}

Application Characteristics

SCC algorithms are applicable when:

• The graph is directed
• Vertices in an SCC share a common property
• Problems require maintaining connectivity information
• Optimization needs involve component-level computation