강의자료/알고리즘

SCC(Strongly Connected Components)-코세라주 알고리즘

원당컴1 2022. 3. 23. 16:08
SCC(Strongly Connected Components) 란

SCC 알고리즘은 방향 그래프에서 그래프의 모든 정점들 간에 양방향으로 경로가 존재하면 강하게 연결 되었다고 하는데 이렇게 연결된 부분그래프를 찾는 알고리즘이다.

위의 그래프에서 a,b,e / f,g / c,d,h 와 같이 3개의 그룹을 찾는 알고리즘

 

SCC가 되기 위한 조건

1. 같은 SCC 내의 임의의 두정점 A,B 사이의 경로가 항상 존재한다.

2. 서로 다른 SCC에서 뽑은 임의의 두 점 A,B 사이의 경로 A->B로 가는 경로와 B->A로 가는 경로는 동시에 존재할 수 없다.(SCC끼리는 사이클이 존재하지 않는다.)

 

 

SCC 알고리즘

- 코세라주 알고리즘

  • 1978년 코사라주가ㅏ 설명하고 1981년 미샤 샤리르가 출판.
  • 두번의 깊이 우선 탐색을 이용하여 구한다.
  • 개념이해와 구현이 타잔의 알고리즘보다 같단하다.

- 타잔 알고리즘

  • 1972년 로버트 타잔이 출판
  • 한번의 깊이 우선 탐색을 이용한다.
  • 개념이해와 구현이 어렵다.

 

 

 

코세라주알고리즘

1. 그래프 G의 각 정점들에 대해서 한번의 dfs 를 수행하면서 스택에 마지막 방문한 위치부터 차곡차곡 쌓아 올린다.

2. 그래프 G의 역방향 그래프를 만든다.

3. 스택에 쌓아 두었던 맨 처음을 꺼내서 역방향 그래프로 갈 수 있는 모든 곳을 방문하면서 하나의 SCC를 만든다.

4. 스택에서 하나씩 꺼내면서 방문하지 않은 정점이라면 3번을 수행하여 하나의 SCC를 만든다.

 

 

그림으로 이해하기

위와 같은 그래프가 있다면 다음과 같이 dfs 로 a부터 방문을 하게된다.

갈 수 있는 마지막 까지 간 후에 다른곳에 갈 곳이 있는 정점(b) 까지 나오면서 스택에 위치를 쌓아 놓으면 f-g-h-d-c 가 쌓인다.

b에서 남은 e 까지 모두 방문후 빠져 나오면서 스택에 쌓아 놓으면 f-g-h-d-e-b-a 가 된다.

 

위의 그래프의 역방향 그래프를 만들어 보자.

스택에서 a를 꺼내서 a에서 갈 수 있는 모든 곳을 가보자.

이렇게 a,e,b 한개의 SCC를 찾아 낸다.

두번째로 스택에서 b,e를 꺼내면 이미 방문한 곳이므로 넘어가고,

d를 꺼내서 d에서 갈 수 있는 모든 곳을 가보자.

이렇게 c,d,h 의 scc를 찾아낸다.

세번째로 h는 이미 방문했으므로 g를 꺼내서 갈 수 있는 곳까지 가 보자.

이렇게 f,g 한개의 scc를 찾아낸다.

 

 

문제풀이

jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=895&sca=99&sfl=wr_hit&stx=1622

 

JUNGOL

 

www.jungol.co.kr

 

 

소스코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <cstdio>
#include <vector>
#include <cstring>
 
#define MAXN 10010
using namespace std;
 
 
int n, m, num, arr[MAXN];
int visited[MAXN], cnt, ans;
vector<int> alist[MAXN], blist[MAXN];
 
void dfs(int node){
    visited[node]=1;
    int i, next;
    for(i=0; i<(int)alist[node].size(); i++){
        next=alist[node][i];
        if(visited[next]) continue;
        dfs(next);
    }
    arr[++num]=node;
}
 
void scc(int node){
    visited[node]=1;
    cnt++;
    int i, next;
    for(i=0; i<(int)blist[node].size(); i++){
        next=blist[node][i];
        if(visited[next]) continue;
        scc(next);
    }
}
 
int main(){
    //freopen("input.txt","r",stdin);
    scanf("%d %d"&n, &m);
    int i, s, e;
    for(i=1; i<=m; i++){
        scanf("%d %d"&s, &e);
        alist[s].push_back(e);
        blist[e].push_back(s);
    }
    for(i=1; i<=n; i++)if(!visited[i]){
        dfs(i);
    }
    memset(visited, 0sizeof(visited));
    for(i=num; i>=1; i--)
    {
        if(!visited[arr[i]]){
            cnt=0;
            s=arr[i];
            scc(s);
            ans=cnt;
        }
    }
    memset(visited, 0sizeof(visited));
    cnt=0;
    scc(s);
    if(cnt==n) printf("%d", ans);
    else printf("0");
    return 0;
}
 
 
cs
사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 통신판매신고번호 : 호 | 사이버몰의 이용약관 바로가기

'강의자료 > 알고리즘' 카테고리의 다른 글

[알고리즘]Union Find  (12) 2022.06.09
[자료구조]스택(Stack)  (8) 2022.04.05
최소 공통조상 LCA(Lowest Common Ancestor) 알고리즘  (12) 2022.02.08
Topological Sorting(위상정렬)  (8) 2022.01.17
[자료구조]트라이(TRIE)  (11) 2022.01.07