티스토리 뷰
https://www.acmicpc.net/problem/2150
2150번: Strongly Connected Component
첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정
www.acmicpc.net
SCC를 새롭게 공부할 수 있었습니다.
SCC는 A, B, C, ... 노드가 방향 그래프로 주어져있을 때 어떤 노드끼리 순회할 수 있는지를 모아놓은 것입니다.
예를 들어 A->B, B->C, C->A 와 같은 그래프가 주어져있으면 A,B,C는 SCC 입니다.
그리고 A->B, B->C, C->A, A->D 와 같은 그래프가 주어져 있으면 A,B,C / D 이렇게 2개의 SCC가 존재합니다.
SCC를 구하기 위해 코사라주 알고리즘을 이용하였습니다.
코사라주 알고리즘은 다음과 같습니다.
준비 : 방향 그래프, 역방향 그래프, 스택
1) 방향 그래프의 임의의 정점부터 DFS를 수행한다. DFS가 끝나는 순으로 스택에 넣는다.
2) 아직 방문하지 않은 정점이 있으면 그 점부터 다시 DFS를 수행하고 끝나는 순으로 스택에 넣는다. (방문한 노드는 재방문 하지 않는다.)
3) 스택의 top부터 역방향 그래프에서 DFS를 수행한다.
4) DFS 과정의 모든 노드를 집합에 담는다.
5) 스택이 empty일 때까지 수행한다. (방문한 노드는 재방문 하지 않는다.)
이 과정을 거치면 각 집합은 SCC가 됩니다.
참고 : https://wondy1128.tistory.com/130
SCC-코사라주 알고리즘(Kosaraju's Algorithm)
방향 그래프(Directed Graph) 에서 SCC (Strongly Connected Component) 를 코사라주 알고리즘을 이용해 구하는 방법이다. ① 주어지는 방향 그래프있다. ② 주어지는 방향 그래프와 역방향을 가지는 역방향 그
wondy1128.tistory.com
코드는 다음과 같습니다.
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 16562 친구비 c++ (0) | 2022.02.07 |
|---|---|
| 백준 11402 이항계수 4 C++ (0) | 2022.01.15 |
| 백준 9576 책 나눠주기 C++ (0) | 2021.12.20 |
| 백준 1202 보석 도둑 C++ (0) | 2021.12.10 |
| 15711 환상의 짝꿍 C++ (0) | 2021.12.05 |