scc

강한 연결 요소 (Strongly Connected Component)

방향 그래프에서 어떤 그룹 X에 있는 임의의 두 정점 A,B에 대해서 항상 A->B로 가는 경로가 존재한다면 그 그룹을 SCC(Strongly Connected Component)라고 한다.

• 백준.2150.Strongly Connected Component

코사라주 알고리즘

시간복잡도는 O(V + E). 두번의 DFS를 수행함.

주어지는 방향 그래프와 주어지는 방향 그래프의 방향을 모두 역으로 뒤집은 역방향 그래프를 생성한다.

그리고 탐색하는 순서대로 정점을 저장할 스택이 필요하다.

우선 정방향 그래프로 DFS를 수행하며 끝나는 순서대로 스택에 삽입한다.

이때 DFS는 모든 정점에 대해서 수행한다.

스택에서 pop하는 순서대로 역방향 그래프로 DFS를 수행하여 한 정점에서 탐색되는 모든 다른 정점들을 같은 SCC로 분류한다.

vector<vector<int>> findSCC(int n, vector<vector<int>> &graph, vector<vector<int>> &rGraph) {
  vector<bool> visited(n, false);
  stack<int> stk;
  vector<vector<int>> scc;

  function<void(int)> dfs = [&](int node) {
    visited[node] = true;
    for (int &next : graph[node]) {
      if (!visited[next]) dfs(next);
    }
    stk.push(node);
  };

  function<void(int, vector<int> &)> dfsR = [&](int node, vector<int> &cycle) {
    visited[node] = true;
    cycle.push_back(node);
    for (int &next : rGraph[node]) {
      if (!visited[next]) dfsR(next, cycle);
    }
  };

  for (int node = 0; node < n; node++) {
    if (!visited[node]) dfs(node);
  }
  visited.assign(n, false);
  while (!stk.empty()) {
    int now = stk.top();
    stk.pop();
    if (visited[now]) continue;

    vector<int> cycle;
    dfsR(now, cycle);
    scc.push_back(cycle);
  }

  return scc;
}

타잔 알고리즘

DFS로 탐색을 한번 실행하므로 시간 복잡도는 O(V + E)이다.

DFS로 탐색할 때 생성되는, DFS 트리의 간선의 정보를 이용한다.

모든 정점에서 수행되는 DFS로 SCC를 구한다.

ALL DFS로 탐색하며 Spanning Tree를 만드며, DFS의 호출 순서에 따라 정점을 stack에 push한다.

이후 간선 분류를 통하여 먼저 호출 되는 정점이 더 높은 우선 순위를 가진다고 생각하자.

이는 먼저 호출되는 정점에 parents값을 낮게 설정해 고려한다.

가장 높이 올라갈 수 있는 정점을 찾는데 이 때 here->there가 교차간선이지만 아직 there가 SCC에 속하지 않는다면 parents(there) 또한 고려한다.

DFS가 끝나기전에 ret과 parents(here)가 같다면 stack에서 pop하면서 here (현재 정점)가 나올 때까지 같은 SCC로 분류한다.

// 정점 방문 순서 기록을 위한 증가하는 변수
int callCount;
// 초기화
int parents[10000 + 1], groupTable[10000 + 1];
memset(discover, -1, sizeof(parents));
memset(groupTable, -1, sizeof(groupTable));

int dfs(int here) {
  parents[here] = callCount;
  int ret = parents[here];
  callCount++;
  st.push(here);

  for (int there : graph[here]) {
    if (parents[there] == -1) {
      int parent = dfs(there);
      ret = min(ret, parent);
    } else if (groupTable[there] == -1) {
      ret = min(ret, parents[there]);
    }
  }

  if (ret == parents[here]) {
    vector<int> connected;

    while (true) {
      int vertex = st.top();
      st.pop();

      groupTable[vertex] = scc.size();
      connected.push_back(vertex);

      if (vertex == here) {
        break;
      }
    }

    sort(connected.begin(), connected.end());
    scc.push_back(connected);
  }
  return ret;
}

for (int vertex = 1; vertex <= V; vertex++) {
  if (discover[vertex] == -1) {
    dfs(vertex);
  }
}
sort(scc.begin(), scc.end(), compare);