SCC (Strongly Connected Component)

SCC, Strongly Connected Component, 강한 결합 요소, 강연결요소

구현

코사라주의 알고리즘(Kosaraju's Algorithm)

코드

(https://www.acmicpc.net/problem/2150, 코드가 발입니다 이해를 좀..., 누가 템플릿으로 만들어주시져)

#include <stdio.h>
#include <vector>
#include <memory.h>
#include <algorithm>

using namespace std;

vector<int> g[10001], rg[10001], rv, ret;
bool visit[10001];
int v;

void dfs(int n)
{
    int i;
    if(visit[n]==false) {
        visit[n] = true;
        for ( i = 0; i < g[n].size(); i++ )
            dfs(g[n][i]);
        rv.push_back(n);
    }
}

void rdfs(int n)
{
    int i;
    if(visit[n]==false) {
        visit[n] = true;
        for ( i = 0; i < rg[n].size(); i++ )
            rdfs(rg[n][i]);
        ret.push_back(n);
    }
}

int main()
{
    int e, a, b, i, j;
    vector< vector<int> > scc;

    scanf("%d%d", &v, &e);
    while(e--) {
        scanf("%d%d", &a, &b);
        g[a].push_back(b);
        rg[b].push_back(a);
    }

    for ( i = 1; i <= v; i++ ) dfs(i);
    memset(visit, 0, sizeof(visit));
    for ( i = rv.size()-1; i >= 0; i-- ) {
        if ( visit[rv[i]] == false ) {
            ret.clear();
            rdfs(rv[i]);
            sort(ret.begin(), ret.end());
            scc.push_back(ret);
        }
    }

    sort(scc.begin(), scc.end());

    printf("%d\n", scc.size());
    for ( i = 0; i < scc.size(); i++ ) {
        for ( j = 0; j < scc[i].size(); j++ )
            printf("%d ", scc[i][j]);
        printf("-1\n");
    }

    return 0;
}

정리

  • 원리
    • 그래프를 dfs 를 통해 스패닝 트리로 만들 경우
    • 스패닝 트리는 DAG 가 된다 (사이클 없는 방향 그래프)
    • 일반적인 DAG에서 말단 노드부터 숫자를 오름차순으로 매기면, 큰번호에서 작은번호로 가는 경우는 없어야 한다. (만약 이러한 경우가 있다면 사이클)
    • 따라서 다음과 같은 로직이 된다.
      • dfs 로 더이상 갈수 없는 노드에 대해서 순차적으로 번호를 매긴 뒤(단말 노드에 대한 오름차순 숫자를 기록)
      • 기록된 숫자의 내림차순서로 dfs 를 역으로 탐색한다. 여기서 나오는 요소의 개수가 scc의 개수가 된다.
  • 내용
  • 주의 사항
    • N 이 많아지면 스택오버플로가 날 수 있다. (n 이 클 경우 dfs 를 스택으로 구현해야 한다)

타잔의 알고리즘 (Tarjan's Algorithm)

  • 준비중

성질

  • SCC 내에 속하는 서로 다른 두 정점은 서로 도달 가능하다.
  • 모든 정점은 단 하나의 SCC 에 속할 수 있다.
  • SCC 를 하나의 정점으로 본다면 DAG(사이클 없는 방향 그래프) 형태로 변환할 수 있다.
  • 다음의 문제와 연관이 있다.

관련 문제

참고 자료

results matching ""

    No results matching ""