글 읽기 - 런타임에러가 어디서 나는지 모르겠습니다..

tjgy9023 5년 전 0

예제도 맞고 몇개 해봤는데 되는데

흠 ㅜㅜ

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		ArrayList<String> ans =new ArrayList<>();
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		Node[] node = new Node[N + 1];
		
		for(int i = 0 ; i < N + 1; i++) {
			node[i] = new Node(i,0);
		}
		Union u = new Union(node);
		
		for(int j = 0; j < M; j++) {
			st = new StringTokenizer(br.readLine());
			int z = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			if(z == 0) {
				u.uni(a,b);
			}else {
				if(u.check(a, b)) {
					ans.add("yes");
				}else {					
					ans.add("no");
				}
			}
		}
		
		for(String str : ans) {
			System.out.println(str);
		}
		
	}
				
}
class Union{
	
	Node[] node;
	public Union(Node[] node) {
		this.node = node;
	}
	
	public int find(int i) {
		if(node[i].parent != i) {
			find(node[i].parent);
		}
		return node[i].parent;
	}
	
	public void uni(int i, int j) {
		int iroot = find(i);
		int jroot = find(j);
		
		if(iroot == jroot) return;
	    
		if(node[iroot].rank > node[jroot].rank) {
	    	node[jroot].parent = iroot;
	    
	    }else if(node[iroot].rank < node[jroot].rank) {
	    	node[iroot].parent = jroot;
	    
	    }else {
	    	node[jroot].parent = iroot;
	    	node[iroot].rank += 1;
	    }
		
	}
	public boolean check(int i, int j) {
		int iroot = find(i);
		int jroot = find(j);
		if(iroot == jroot) return true;
		return false;
	}
}
class Node{
	int parent,rank;

	public Node(int parent, int rank) {
		super();
		this.parent = parent;
		this.rank = rank;
	}
}

djm03178 5년 전 1

find 메서드를 잘못 구현했기 때문입니다.

어떤 노드의 루트를 구하려면 node[i].parent != i 인 경우 find(node[i].parent)를 반환해야 하는데, 자신의 부모를 변경하지 않고 그대로 node[i].parent를 반환하면 그 노드는 해당 set의 루트가 아닐 수도 있습니다.

따라서 54번째 줄은 node[i].parent = find(node[i].parent); 로 바꿔줘야 합니다.

tjgy9023 5년 전 0

감사합니다!!!!

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

문제

문제

출처

ICPC

런타임에러가 어디서 나는지 모르겠습니다..

tjgy9023 5년 전 0

djm03178 5년 전 1

tjgy9023 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말