글 읽기 - 타잔알고리즘으로 SCC를 구해 문제를 풀었으나 틀렸습니다ㅜㅜ

jaejin0209 4년 전 0

인터넷에서 2-SAT 풀이 알고리즘을 대략적으로 이해한 후 직접 프로그래밍해보았으나 틀렸습니다...ㅜㅜ

아무리 디버깅을 해봐도 문제가 될 여지가 없는것 같은데 왜 틀렸다고 나오는지 꼭 알고싶습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int n, m;
	static ArrayList<Integer>[] graph;

	public static void main(String[] args) throws IOException {
		input();
		System.out.print(solve() ? '1' : '0');
	}

	static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		graph = new ArrayList[2 * n + 1];
		for (int i = 0; i <= 2 * n; i++) {
			graph[i] = new ArrayList<Integer>();
		}
		for (int j = 0; j < m; j++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph[n - a].add(n + b);
			graph[n - b].add(n + a);
		}
	}

	static boolean solve() {
		ArrayList<Integer> dfs = new ArrayList<Integer>();
		boolean[] check = new boolean[2 * n + 1];
		for (int i = 0; i <= 2 * n; i++) {
			if (!check[i]) {
				dfs(i, check, dfs, graph);
			}
		}
		ArrayList<Integer>[] rGraph = new ArrayList[2 * n + 1];
		for (int i = 0; i <= 2 * n; i++) {
			rGraph[i] = new ArrayList<Integer>();
		}
		for (int i = 0; i <= 2 * n; i++) {
			for (int j : graph[i]) {
				rGraph[j].add(i);
			}
		}
		Arrays.fill(check, false);
		int number = 1;
		int[] scc = new int[2 * n + 1];
		for (int i = 2 * n; i >= 0; i--) {
			if (check[i]) {
				continue;
			}
			ArrayList<Integer> arr = new ArrayList<Integer>();
			dfs(dfs.get(i), check, arr, rGraph);
			for (int j : arr) {
				scc[j] = number;
			}
			number++;
		}
		boolean ans = true;
		for (int i = 1; i <= n; i++) {
			if (scc[n - i] == scc[n + i] && scc[n - i] > 0) {
				ans = false;
				break;
			}
		}
		return ans;
	}

	static void dfs(int a, boolean[] check, ArrayList<Integer> arr, ArrayList<Integer>[] g) {
		check[a] = true;
		for (int i : g[a]) {
			if (!check[i]) {
				dfs(i, check, arr, g);
			}
		}
		arr.add(a);
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

타잔알고리즘으로 SCC를 구해 문제를 풀었으나 틀렸습니다ㅜㅜ

jaejin0209 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말