알고리즘 : SCC
Strongly Connected Component
| 시간 제한 | 메모리 제한 |
| 2초 | 512 MB |
문제
방향 그래프가 주어졌을 때, 그 그래프를 SCC들로 나누는 프로그램을 작성하시오.
방향 그래프의 SCC는 우선 정점의 최대 부분집합이며, 그 부분집합에 들어있는 서로 다른 임의의 두 정점 u, v에 대해서 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재하는 경우를 말한다.
예를 들어 위와 같은 그림을 보자. 이 그래프에서 SCC들은 {a, b, e}, {c, d}, {f, g}, {h} 가 있다. 물론 h에서 h로 가는 간선이 없는 경우에도 {h}는 SCC를 이룬다.
입력
첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이다. 이때 방향은 A → B가 된다.
정점은 1부터 V까지 번호가 매겨져 있다.
출력
첫째 줄에 SCC의 개수 K를 출력한다. 다음 K개의 줄에는 각 줄에 하나의 SCC에 속한 정점의 번호를 출력한다. 각 줄의 끝에는 -1을 출력하여 그 줄의 끝을 나타낸다. 각각의 SCC를 출력할 때 그 안에 속한 정점들은 오름차순으로 출력한다. 또한 여러 개의 SCC에 대해서는 그 안에 속해있는 가장 작은 정점의 정점 번호 순으로 출력한다.
예제 입력 1
7 9
1 4
4 5
5 1
1 6
6 7
2 7
7 3
3 7
7 2
예제 입력 2
3
1 4 5 -1
2 3 7 -1
6 -1
풀이
SCC : https://www.youtube.com/watch?v=M9d_DthAxwg
import java.io.*;
import java.util.*;
public class Main {
static ArrayList<Integer>[] route;
static ArrayList<Integer>[] reverseRoute;
static ArrayList<ArrayList<Integer>> answerList = new ArrayList<>();
static boolean[] visited;
static int[] numCnts;
static int numCnt = 1;
private static void dfs(int cur) {
for(int next: route[cur]) {
if(!visited[next]) {
visited[next] = true;
dfs(next);
}
}
numCnts[numCnt++] = cur;
}
private static void dfs2(int cur) {
answerList.get(answerList.size() - 1).add(cur);
for(int next: reverseRoute[cur]) {
if(!visited[next]) {
visited[next] = true;
dfs2(next);
}
}
}
@SuppressWarnings("unchecked")
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int V = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
route = new ArrayList[V+1];
reverseRoute = new ArrayList[V+1];
for(int i = 1; i <= V; i++) {
route[i] = new ArrayList<>();
reverseRoute[i] = new ArrayList<>();
}
visited = new boolean[V+1];
numCnts = new int[V+1];
for(int i=1; i <= E; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
route[from].add(to);
reverseRoute[to].add(from);
}
// DFS를 하면서, 빠져나오는 순서대로 시간을 기록
for(int i=1; i <= V; i++) {
if(!visited[i]) {
visited[i] = true;
dfs(i);
}
}
visited = new boolean[V+1];
// 뒤집은 그래프에 대해서, 빠져나오는 시간이 큰 노느부터 순회
// 이 때 만나는 노드들이 모두 같은 그룹임.
for(int i=V; i>= 1; i--) {
if(!visited[numCnts[i]]) {
visited[numCnts[i]] = true;
answerList.add(new ArrayList<Integer>());
dfs2(numCnts[i]);
}
}
for(ArrayList<Integer> next: answerList) {
Collections.sort(next);
}
answerList.sort((o1, o2) -> o1.get(0) - o2.get(0));
System.out.println(answerList.size());
for(int i=0; i < answerList.size(); i++) {
for(int next: answerList.get(i)) {
System.out.print(next + " ");
}
System.out.println("-1");
}
}
}출처
- 백준 2150번 : https://www.acmicpc.net/problem/2150
'알고리즘' 카테고리의 다른 글
| BFS/미로 탈출 백준 14923번 (2) | 2023.10.28 |
|---|---|
| 그래프/파티 백준 1238번 (0) | 2023.10.04 |
| DP/1,2,3 더하기 백준 9095번 (0) | 2022.10.09 |
| DFS/웜바이러스 백준 2606번 (0) | 2022.02.28 |
| 스택/괄호의값 백준 2504번 (0) | 2022.02.13 |
