글 읽기 - 유니온 파인드로 풀었는데 왜 20%에서 틀렸을까요 ??;;

20140058 3년 전 0

원리는 만약 사이클이생기는경우 부모를 0으로 만들어버리는 겁니다.

질문게시판의 테스트케이스를 다 집어넣어도 통과하는데 제출하면 20%에서 자꾸막히네요 ..

import java.io.*;
import java.util.*;


class E{
	int s,e;
	public E(int s,int e) {
		this.s=s;
		this.e=e;
	}
}
public class Main {

	static int parent[];
	static Queue<E> q;
	static int N,M;
	static int Test;
	static boolean pCnt[];
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	String input[];
    	Test=0;
    	while(true) {
    		input = br.readLine().split(" ");
    		N = Integer.parseInt(input[0]);
    		M = Integer.parseInt(input[1]);
    		Test++;
    		if(N+M==0)
    			break;
    		parent = new int[N+1];
    		pCnt = new boolean[N+1];
    		for(int i=0;i<=N;i++) 
    			parent[i] = i;
    		q = new LinkedList<E>();
    		for(int i=1;i<=M;i++) {
    			input = br.readLine().split(" ");
    			int s = Integer.parseInt(input[0]);
    			int e = Integer.parseInt(input[1]);
    			
    			q.add(new E(s,e));
    		}
    		
    		while(!q.isEmpty()) {
    			E tmp = q.poll();
    			int s =tmp.s;
    			int e =tmp.e;
    			
    			int a = find(s);
    			int b = find(e);
    			
    			if(a==0 || b==0) {
    				parent[s] = 0;
    				parent[e] = 0;
    				continue;
    			}
    			if(a==b) {
    				parent[a]=0;
    				parent[b]=0;
    				find(s);find(e);
    				continue;
    			}
    			
    			union(s,e);
    		}
    		
    		for(int i=1;i<=N;i++) 
    			find(i);
    		for(int i=1;i<=N;i++) {
    			if(parent[i] !=0)
    				pCnt[parent[i]]=true;
    		}
    		int cnt=0;
    		
    		for(int i=1;i<=N;i++) 
    			if(pCnt[i])
    				cnt++;
    		if(cnt==0)
    			System.out.println("Case "+Test+": No trees.");
    		else if(cnt==1)
    			System.out.println("Case "+Test+": There is one tree.");
    		else
    			System.out.println("Case "+Test+": A forest of "+cnt+" trees");

    	}
    	
    	
    	
    }
	static int find(int a) {
		if(a==parent[a])
			return a;
		parent[a] = find(parent[a]);
		return parent[a];
	}
	static void union(int a,int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		if(aRoot!=bRoot) 
			parent[aRoot] = b;

	}
}

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

문제

문제

출처

ICPC

유니온 파인드로 풀었는데 왜 20%에서 틀렸을까요 ??;;

20140058 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말