Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

37. 강한 연결 요소

Strongly connected component를 다뤄 봅시다.

3. 축구 전술

3977번

SCC를 사용하는 문제 2

이번 문제는 경기장을 여러 개의 구역으로 나누고, 어떤 선수가 A구역에서 B구역으로 이동하게 하는 움직임을 (A, B)로 표현한다고 할 때, 다른 모든 구역에 도달할 수 있는 시작 구역을 찾아내는 문제이다.

SCC를 찾는 알고리즘은 크게 이 두가지 방법이다.

• 타잔 알고리즘
  모든 정점에 대해 DFS를 수행하여 SCC를 찾는 알고리즘으로, 코사라주 알고리즘에 비해 적용이 더 쉽다고 한다.
  ① 인접 정점에 방문하며 자기 자신을 스택에 넣고, 재귀적으로 DFS를 수행한다.
  ② 인접 정점에 방문했지만, 아직 처리중인 상태일 경우, 작은 값으로 부모값을 갱신한다.
  ③ 부모 노드의 DFS가 끝난 경우에는, 자신의 id값이 스택에서 나올 때까지 스택에 있는 노드들을 pop하고 scc 배열에 추가한다.
  ④ 만들어진 하나의 scc를 전체 SCC 배열에 추가한다.
  (구현이 더 어렵지만, 활용도는 더 높다고 한다.)
  

• 코사라주 알고리즘
  주어진 방향 그래프의 역방향 그래프와 스택을 사용하여 SCC를 구하는 알고리즘이다. 방향, 역방향 그래프가 동일한 SCC를 구성한다는 것을 이용한 방법이다.
  ① 주어지는 방향 그래프와 그 그래프의 역방향 그래프를 만든다.
  ② 정점을 담을 스택을 만들고 임의의 정점부터 DFS를 수행한다.
  ③ DFS가 끝나는 순서대로 스택에 삽입하고, 아직 방문하지 않은 정점에 대해 DFS를 수행한다.
  ④ 모든 정점이 스택에 담긴 후에는 스택을 pop하여 나오는 정점부터 역방향 그래프에서 DFS를 수행한다.. 이미 방문한 정점은 pop만 시행한다.
  ⑤ 이때 탐색되는 모든 정점을 SCC로 묶는다.
  이것을 스택이 빌 때까지 진행한다.
  (타잔 알고리즘에 비해 구현이 더 쉬운 편이라고 한다.)

저번 SCC 문제들과 유사하고, 조금만 변형해서 풀 수 있었다.

Java / Python

• Java

import java.io.*;
import java.util.*;

public class Main {
	static int scc_total, num;
	static ArrayList<Integer>[] edges;
	static int[] order, scc_arr;
	static boolean[] visit; // SCC 확정된 정점 확인
	static Stack<Integer> stack;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int T = Integer.parseInt(br.readLine());

		for (int t = 0; t < T; t++) {
			if (t != 0) {
				br.readLine();
			}

			st = new StringTokenizer(br.readLine());

			int N = Integer.parseInt(st.nextToken()); // 정점의 개수
			int M = Integer.parseInt(st.nextToken()); // 간선의 개수

			edges = new ArrayList[N + 1];

			for (int i = 0; i < N + 1; i++) {
				edges[i] = new ArrayList<>();
			}

			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());

				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());

				edges[a].add(b);
			}

			scc_arr = new int[N + 1];
			order = new int[N + 1];
			visit = new boolean[N + 1];
			scc_total = num = 0;
			stack = new Stack<>();

			for (int i = 0; i < N; i++) {
				if (order[i] == 0)
					SCC(i);
			}

			int[] indegree = new int[scc_total];

			for (int i = 0; i < N; i++) {
				int s = edges[i].size();

				for (int j = 0; j < s; j++) {
					int end = edges[i].get(j);

					if (scc_arr[end] != scc_arr[i])
						indegree[scc_arr[end]]++;
				}

			}
			int cnt = 0;
			int tag = 0;

			for (int i = 0; i < scc_total; i++) {
				if (indegree[i] == 0) {
					tag = i;
					cnt++;
				}
			}

			if (cnt > 1)
				bw.write("Confused\n");
			else {
				for (int i = 0; i < N; i++) {
					if (scc_arr[i] == tag)
						bw.write(i + "\n");
				}
			}
			bw.write("\n");
		}
		bw.flush();
		bw.close();
		br.close();
	}

	private static int SCC(int idx) {
		order[idx] = ++num;
		stack.add(idx);
		int root = order[idx];

		for (int i = 0; i < edges[idx].size(); i++) {
			int temp = edges[idx].get(i);
			if (order[temp] == 0)
				root = Math.min(root, SCC(temp));
			else if (!visit[temp])
				root = Math.min(root, order[temp]);
		}

		if (root == order[idx]) {
			while (true) {
				int top = stack.pop();
				scc_arr[top] = scc_total;
				visit[top] = true;
				if (top == idx)
					break;
			}
			scc_total++;
		}
		return root;
	}
}

• Python

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# 정방향 dfs, dfs 가 종료되는 노드를 stack에.
def dfs(node, visit, stack):
    visit[node] = 1
    for now in graph[node]:
        if visit[now] == 0:
            dfs(now, visit, stack)
    stack.append(node)

# 역방향 dfs, 탐색하는 순서대로 stack에.
def reverse_dfs(node, visit, stack):
    visit[node] = 1
    ids[node] = idx
    stack.append(node)
    for now in reverse_graph[node]:
        if visit[now] == 0:
            reverse_dfs(now, visit, stack)

T = int(input())
while T:
    inline = input()
    if inline == '\n':
        continue
    N, M = map(int, inline.split())
    graph = [[] for _ in range(N)]
    reverse_graph = [[] for _ in range(N)]

    for _ in range(M):
        a, b = map(int, input().split())
        # 정방향 그래프, 역방향 그래프 추가
        graph[a].append(b)
        reverse_graph[b].append(a)
    stack = []
    visit = [0] * N
    # 모든 노드에서 dfs를 수행.
    for i in range(N):
        if visit[i] == 0:
            dfs(i, visit, stack)
            
    result = [[] for _ in range(N)]
    visit = [0] * N
    idx = -1
    ids = [-1] * N
    
    while stack:
        # pop되는 요소에서 역방향 dfs, scc를 결과에.
        ssc = []
        node = stack.pop()
        if visit[node] == 0:
            idx += 1
            reverse_dfs(node, visit, ssc)
            result[idx] = ssc
    scc_indegree = [0] * (idx + 1)

    for i in range(N):
        for ed in graph[i]:
            if ids[i] != ids[ed]:
                scc_indegree[ids[ed]] += 1
    cnt = 0
    temp = []
    for i in range(len(scc_indegree)):
        if scc_indegree[i] == 0:
            for r in result[i]:
                temp.append(r)
            cnt += 1
    if cnt == 1:
        for i in sorted(temp):
            print(i)
    else:
        print("Confused")
    print()
    T -= 1