-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
친구인가?(Union&Find) 첫 case1에서 타임리밋뜨는 이유
23.03.01 11:57 작성 23.03.01 11:59 수정 조회수 206
0
채점 결과 태스트 케이스2~5까지는 정답으로 나옵니다.
4개 모두 200ms안에 끝납니다
반면에 가장 테스트 케이스 크기가 작을 case1에서는 타임리밋이 뜹니다
이유는 무엇이고 해결책은 무엇일까요?
import java.util.*;
public class Main {
static String answer = "NO";
static int N,M;
static int[] ch,dis;
public void BFS(int t1, int t2, ArrayList<ArrayList<Integer>> arr) {
Queue<Integer> Q = new LinkedList<>();
Loop:for(int i = 1;i<=N;i++) {
if(ch[i] == 0) {
Q.offer(i);
while(!Q.isEmpty()) {
int tmp = Q.poll();
ch[tmp] = 1;
dis[tmp] = 1;
if(dis[t1] == 1 && dis[t2]==1) {
answer = "YES";
break Loop;
}
int len = arr.get(tmp).size();
for(int j = 0;j<len;j++) {
int n = arr.get(tmp).get(j);
Q.offer(n);
}
}
Arrays.fill(dis, 0);
}
}
}
public static void main(String[] args){
Scanner in=new Scanner(System.in);
N = in.nextInt();
M = in.nextInt();
ch = new int[N+1];
dis = new int[N+1];
ArrayList<ArrayList<Integer>> arr = new ArrayList<>();
for(int i = 0;i<=N;i++) {
arr.add(new ArrayList<Integer>());
}
for(int i = 0;i<M;i++) {
int a = in.nextInt();
int b= in.nextInt();
arr.get(a).add(b);
}
int t1 = in.nextInt();
int t2 = in.nextInt();
Main T = new Main();
T.BFS(t1, t2, arr);
System.out.print(answer);
}
}
답변을 작성해보세요.
0
김태원
지식공유자2023.03.07
안녕하세요^^
테스트케이스 1번입니다. 디버스해보세요.
20 22
18 9
4 15
12 16
9 10
10 7
14 9
13 3
17 5
6 1
1 14
12 4
9 11
7 5
17 4
6 17
12 9
18 10
17 8
11 18
7 19
4 3
3 4
10 15
답변 1