strawberry333   3년 전

안녕하세요! 이분그래프 문제를 풀다가...

테스트케이스도 맞고 정답인것 같기도 한데 ㅠㅠ 왜 런타임 오류가 나는지 모르겠습니다. ㅠㅠ.......

혹시라도 아래 코드 보시고 원인을 아시는 분은...

알려주시면 정말 감사드리겠습니다!! ㅠ_ㅠ


===========================================================

#1707 이분 그래프

문제

 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 
 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

 입력
 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 
 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 
 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 N까지 차례로 번호가 붙어 있다. 
 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 
 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.

 출력
 K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.


===========================================================

제가 제출한 코드


public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int K = sc.nextInt(); // 테스트 케이스 K

//

for (int i = 1; i <= K; K++) { // 각 테스트 케이스에 대해

int V = sc.nextInt();// 정점의 갯수 V , V <= 2만 (1~N)
int E = sc.nextInt();// 간선의 갯수 E , E <= 20만 ...;;

boolean result = true;

int[] color = new int[V + 1];
// 초기값 0 저장되 있음.

ArrayList<Integer>[] a = (ArrayList<Integer>[]) new ArrayList[V + 1];
// 인접 리스트 저장하는 어레이리스트.

for (int j = 0; j < V + 1; j++) { // ★

a[j] = new ArrayList<Integer>();

}

for (int j = 1; j <= E; j++) {
int u = sc.nextInt(); // 시작점
int v = sc.nextInt(); // 끝점
a[u].add(v);
a[v].add(u);

} // 모든 간선 저장 완료.

for (int j = 1; j <= V; j++) {
Collections.sort(a[j]);

}

for (int j = 1; j <= V; j++) {
// 모든 정점에 대해
if (color[j] == 0) {
// 체크안된정점이 있다면 dfs 실행.(끝나고 체크안된거 잇을수잇음)
dfs(j, a, color, 1);
}
}

// 시작
// 정점 1을 시작으로 color 배열 가지고 dfs 하면서 돌아댕기기

for (int j = 1; j <= V; j++) {
// 모든 간선에 대해 시작점과 끝점 색이 다른지 확인
// <=> 모든 정점에 대해 연결점이 다른지 확인.

for (int n = 0; n < a[j].size(); n++) {

if (color[j] == color[a[j].get(n)])

result = false;

}
}

if (result)
System.out.println("YES");
else
System.out.println("NO");

}
}

static void dfs(int x, ArrayList<Integer>[] arraylist, int[] c, int owncolor) {
// 정점, 어레이리스트전달, 배열전달, 현재 정점의 색상

// if (c[x] != 0) { // 이미 색칠되있으면 return.
// return;
// }

for (int y : arraylist[x]) {

if (c[y] == 0) {
dfs(x, arraylist, c, 3 - owncolor);
// c[x] = 3 - owncolor;
}

}
}
}

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