문제
방향 그래프가 주어졌을 때, 그 그래프를 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에 대해서는 그 안에 속해있는 가장 작은 정점의 정점 번호 순으로 출력한다.
예제 입력 | 예제 출력 |
7 9 1 4 4 5 5 1 1 6 6 7 2 7 7 3 3 7 7 2 |
3 1 4 5 -1 2 3 7 -1 6 -1 |
풀이
강한 결합 요소 알고리즘 SCC 의 가장 기초적인 문제이다.
기초지만 나는 못풀었다. 넘 어렵따.
알고리즘을 품기에는 내 용량이 너무 작은 듯 싶다.
나중에 다시 또 풀어봐야지~!
[ JAVA ]
import java.util.*; | |
public class beakjoon_2150 { | |
static int V, E; | |
static ArrayList<Integer> [] linked,answer; | |
static int [] order; | |
static boolean [] visited; | |
static int size,num; | |
static Stack <Integer> stack; | |
public static void main(String [] args){ | |
Scanner scan = new Scanner(System.in); | |
V = scan.nextInt(); | |
E = scan.nextInt(); | |
linked = new ArrayList[V+1]; | |
answer = new ArrayList[V+1]; | |
for(int i=0; i<V+1; i++){ | |
linked[i] = new ArrayList<>(); | |
answer[i] = new ArrayList<>(); | |
} | |
for(int i=0; i<E; i++){ | |
int A = scan.nextInt(); | |
int B = scan.nextInt(); | |
linked[A].add(B); | |
} | |
order = new int[V+1]; | |
visited = new boolean[V+1]; | |
size = 0; | |
num = 0; | |
stack = new Stack<>(); | |
for(int i=1; i<V+1; i++){ | |
if(order[i]==0) | |
SCC(i); | |
} | |
System.out.println(size); | |
for(int i=1; i<V+1; i++){ | |
if(answer[i].size() > 0){ | |
for(int j=0; j<answer[i].size(); j++){ | |
System.out.print(answer[i].get(j) + " "); | |
} | |
System.out.print("-1"); | |
System.out.println( ); | |
} | |
} | |
} | |
public static int SCC(int index){ | |
order[index] = ++num; | |
stack.add(index); | |
int root = order[index]; | |
for(int i=0; i<linked[index].size(); i++){ | |
int temp = linked[index].get(i); | |
if(order[temp] == 0) | |
root = Math.min(root, SCC(temp)); | |
else if(!visited[temp]) | |
root = Math.min(root, order[temp]); | |
} | |
if(root == order[index]){ | |
ArrayList<Integer> tempArr = new ArrayList<>(); | |
while(true){ | |
int top = stack.pop(); | |
tempArr.add(top); | |
visited[top] = true; | |
if(top == index) break; | |
} | |
Collections.sort(tempArr); | |
int min = Collections.min(tempArr); | |
answer[min] = tempArr; | |
size++; | |
} | |
return root; | |
} | |
} | |

'알고리즘' 카테고리의 다른 글
[ 프로그래머스 ] 땅따먹기 (0) | 2021.03.09 |
---|---|
[ 백준 4196 ] 도미노 (0) | 2021.03.05 |
[ 백준 1671 ] 상어의 저녁식사 (0) | 2021.03.03 |
[ 백준 11376 ] 열혈강호2 (0) | 2021.03.01 |
[ 백준 11375 ] 열혈강호 (0) | 2021.03.01 |
댓글