Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

37. 강한 연결 요소

Strongly connected component를 다뤄 봅시다.

7. 아이돌

3648번

상근이가 진출하면서 동시에 2-SAT을 성립시킬 수 있는지 판별하는 문제

아이돌 예선에 참가하는 상근이가 심사위원의 의심을 받지 않으면서, 다음 라운드에 진출하는 목록을 만들 수 있는지를 알고 싶어 한다. 당연히 이 목록에는 상근이가 포함되어 있어야 한다. 각 심사위원이 투표한 결과가 주어졌을 때, 상근이가 포함된 다음 라운드 진출 목록을 만들 수 있는지 없는지를 구하는 프로그램을 작성하는 문제이다.
심사위원이 내야하는 두 개의 표 중 하나는 결과에 영향을 미쳐야하므로, 하나의 OR 절로 묶어낼 수 있고, 모든 심사위원의 투표 결과로 진출 목록을 만들어내야 하기 때문에 2-SAT 문제로 볼 수 있다.
진출 목록을 만들 수 있는지 없는지 확인하고 상근이도 진출 목록에 포함시킨다.

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 N, V, num;
	static ArrayList<Integer>[] graph;
	static int[] parent, CNF;
	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;

		while (true) {
			String input = br.readLine();
			if (input == null)
				break;
			st = new StringTokenizer(input, " ");

			N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());

			parent = new int[2 * N + 1];
			visit = new boolean[2 * N + 1];
			stack = new Stack<>();
			num = 0;
			V = 0;
			CNF = new int[2 * N + 1];
			graph = new ArrayList[2 * N + 1];

			for (int i = 0; i < 2 * N + 1; i++) {
				graph[i] = new ArrayList<>();
			}
			graph[validate(-1)].add(1);

			while (M-- > 0) {
				st = new StringTokenizer(br.readLine(), " ");

				int u = Integer.parseInt(st.nextToken());
				int v = Integer.parseInt(st.nextToken());

				graph[validate(-u)].add(validate(v));
				graph[validate(-v)].add(validate(u));
			}

			for (int i = 1; i < 2 * N + 1; i++) {
				if (!visit[i]) {
					SCC(i);
				}
			}

			bw.write(printR());
		}

		bw.flush();
		bw.close();
		br.close();
	}

	private static int validate(int n) {
		return (0 < n && n < N + 1) ? n : -n + N;
	}
	
	private static String printR() {
		for (int i = 1; i < N + 1; i++) {
            if (CNF[i] == CNF[i + N]) return "no\n";
        }
        return "yes\n";
	}

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

		for (int next : graph[idx]) {
			if (parent[next] == 0)
				root = Math.min(root, SCC(next));
			else if (!visit[next])
				root = Math.min(root, parent[next]);
		}

		if (root == parent[idx]) {
			while (!stack.isEmpty()) {
				int top = stack.pop();
				CNF[top] = V;
				visit[top] = true;
				if (top == idx)
					break;
			}
			V++;
		}
		return root;
	}
}

• Python

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

def SCC(node):
    global idx, scc_num
    visit[node] = idx
    idx += 1
    stack.append(node)
    root = visit[node]
    for nxt in graph[node]:
        if not visit[nxt]:
            root = min(root, SCC(nxt))
        elif not check[nxt]:
            root = min(root, visit[nxt])
    if root == visit[node]:
        cur_scc = []
        while True:
            top = stack.pop()
            check[top] = True
            cur_scc.append(top)
            CNF[top] = scc_num
            if top == node:
                break
        scc_num+=1
        scc_arr.append(cur_scc)
    return root

while True:
    inputline  = input()
    if inputline == "":
        break
    N, M = map(int, inputline.split())
    graph = [[] for _ in range(2*N)]
    for _ in range(M):
        a, b = map(int, input().split())
        if a < 0 :  a = N - a
        if b < 0 : b = N -b
        a -= 1
        b -= 1
        graph[(a+N)%(2*N)].append(b)
        graph[(b+N)%(2*N)].append(a)
    graph[N].append(0)

    visit = [False] * (2*N)
    check = [False] * (2*N)
    idx = 1
    scc_num = 0
    CNF = [-1]*(2*N)
    stack = []
    scc_arr = []

    for i in range(2*N):
        if not visit[i]:
            SCC(i)
    for i in range(N):
        if CNF[i] == CNF[N+i]:
            print("no")
            break
    else:
        print("yes")