글 읽기 - 어디서 틀린건지 모르겠습니다.

wndud0627 3년 전 0

union find 로 풀었는데

어디서 틀린건지 모르겠네요.

반례가 있나요?

import java.io.*;
import java.util.*;
class prob{
	static boolean flag=true;
	static int N;
	static int M;
	static int[] parent;
	static void solve() throws IOException{
		StringTokenizer st;
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(br.readLine());
		M=Integer.parseInt(br.readLine());
		parent=new int[N+1];
		parent_count=new int[N+1];
		for(int i=1; i<parent.length; i++)
			parent[i]=i;
		for(int i=1; i<=N; i++) {
			st=new StringTokenizer(br.readLine());
		for(int j=1; j<=N; j++) {
			int order=Integer.parseInt(st.nextToken());
			if(order==1)
				union(i,j);
			}
		}
		st=new StringTokenizer(br.readLine());
		int root=parent[Integer.parseInt(st.nextToken())];
		while(st.hasMoreTokens()) {
			if(root!=find_set(Integer.parseInt(st.nextToken()))) {
				flag=false;
				break;
			}
		}
		if(flag)
			System.out.print("YES");
		else
			System.out.print("No");

	}
	static int find_set(int x) {
		if(parent[x]==x)
			return x;
		return parent[x]=find_set(parent[x]);
	}
	static void union(int x,int y) {

		x=find_set(x);
		y=find_set(y);
		if(x==y)
			return;
		if(x!=y) {
			if(x<y) {
				parent[y]=x;
			}
			else
			{
				parent[x]=y;
			}
		}
	}
}
public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		prob.solve();
	}

}

rlagjqm2 2년 전 0

26번째 줄에 root 노드를 찾는 부분이 잘못된거 같아요.

parent 배열에서 인덱스로 첫번째에 계획된 도시를 넣는다면
거기서 나오는 요소값은 root노드가 아니라 그냥 부모노드로 나오기 때문에 틀린것 같습니다.

저렇게 하실꺼면

26번째 줄을

int root=fint_set(Integer.parseInt(st.nextToken()));

이렇게 바꾸셔야 할꺼 같아요

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

문제

문제

출처

ICPC

어디서 틀린건지 모르겠습니다.

wndud0627 3년 전 0

rlagjqm2 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말