Strongly Connected Component

Jun 20, 23

Strongly Connected Component

이미지

A directed graph is strongly connected if there is a path between all pairs of vertices. A strongly connected component (SCC) of a directed graph is a maximal strongly connected subgraph.

code

#include<iostream>

#include<stack>

#define v 5
using namespace std;

int graph[v][v];

int min(int a, int b) {
  return (a < b) ? a : b;
}

void findComponent(int u, int disc[], int lowLink[], stack < int > & stk, bool stkItem[]) {
  static int time = 0;
  disc[u] = lowLink[u] = ++time;
  stk.push(u);
  stkItem[u] = true;

  for (int v = 0; v < v; v++) {
    if (graph[u][v]) {
      if (disc[v] == -1) {
        findComponent(v, disc, lowLink, stk, stkItem);
        lowLink[u] = min(lowLink[u], lowLink[v]);
      } else if (stkItem[v])
        lowLink[u] = min(lowLink[u], disc[v]);
    }
  }

  int poppedItem = 0;
  if (lowLink[u] == disc[u]) {
    while (stk.top() != u) {
      poppedItem = stk.top();
      cout << poppedItem << " ";
      stkItem[poppedItem] = false;
      stk.pop();
    }
    poppedItem = stk.top();
    cout << poppedItem << endl;
    stkItem[poppedItem] = false;
    stk.pop();
  }
}

void strongConComponent() {
  int disc[v], lowLink[v];
  bool stkItem[v];
  stack < int > stk;

  for (int i = 0; i < v; i++) {
    disc[i] = lowLink[i] = -1;
    stkItem[i] = false;
  }

  for (int i = 0; i < v; i++)
    if (disc[i] == -1)
      findComponent(i, disc, lowLink, stk, stkItem);
}

int main() {
  strongConComponent();
}

reference: https://www.topcoder.com/thrive/articles/tarjans-algorithm-for-strongly-connected-components