글 읽기 - bfs 스페셜 저지..70%에서 틀렸습니다 뜹니다ㅠㅠ

kp6069 4년 전 0

반례 좀 찾아주실 수 있을까요 ㅠㅠ 너무 답답하네요

import java.util.*;

public class N_16940 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner s = new Scanner(System.in);
		int N = s.nextInt();
		ArrayList<Integer>[] adlist = (ArrayList<Integer>[]) new ArrayList[N + 1];
		for (int i = 1; i <= N; i++)
			adlist[i] = new ArrayList<Integer>();
		for (int i = 0; i < N - 1; i++) {
			int a = s.nextInt();
			int b = s.nextInt();
			adlist[a].add(b);
			adlist[b].add(a);
		}
		ArrayList<Integer> ex = new ArrayList<Integer>();
		for (int i = 0; i < N; i++)
			ex.add(s.nextInt());

		int[] c = new int[N + 1]; // 방문 여부 저장
		Queue<Integer> q = new LinkedList<Integer>();
		// bfs
		c[ex.get(0)] = 1;
		q.offer(ex.get(0));
		ex.remove(0);
		while (!q.isEmpty()) {
			int a = q.poll();
			int num = 0;
			for (int k : adlist[a]) {
				if (c[k] == 0)
					num++;
			}
			for (int i = 0; i < num; i++) {
				if (adlist[a].contains(ex.get(0)) && c[ex.get(0)] == 0) {
					q.offer(ex.get(0));
					c[ex.get(0)] = 1;
					ex.remove(0);
				} else {
					System.out.println(0);
					System.exit(0);
				}
			}
		}
		if (ex.size() == 0)
			System.out.println(1);
		else
			System.out.println(0);
	}

}

112ckek 4년 전 4

방문순서가 1로 시작하지 않는경우를 체크해야합니다.

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

문제

문제

출처

ICPC

bfs 스페셜 저지..70%에서 틀렸습니다 뜹니다ㅠㅠ

kp6069 4년 전 0

112ckek 4년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말