글 읽기 - 싸이클을 Union-find으로 시도했는데 9%에서 막히네요 도와주세요!!

loosie999 2년 전 0

DFS로는 간단히 풀리는데 괜히 서로소조합으로 해볼려고 했다가 헤매고있네요..

ranks 배열은 i를 부모로 삼는 자식노드의 수를 저장하도록 설계했습니다.

예로, 1->3->4 이면 ranks[1] = 2 이렇게 싸이클을 찾아내어

ranks의 값이 0이아닌 값을 싸이클로 판별하여 출력하게 했습니다.

아래의 예제도 1이 출력되는데 다른 반례를 못찾겠네요 ㅠㅠ

1
4
3 4 2 1

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

public class Main {

	static int[] parents;
	static int[] ranks;
	static int cycle;
    
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		StringBuilder sb = new StringBuilder();
        
		int t = Integer.parseInt(br.readLine());
		for(int test=0; test<t; test++) {
			int n = Integer.parseInt(br.readLine());
            
            // --------------초기화--------------------
			parents = new int[n+1];
			ranks = new int[n+1];
			cycle=0;
			for(int i=1; i<n+1; i++) {
				parents[i] = i;
			}
			
			st = new StringTokenizer(br.readLine());
			
            // -------------- union-set --------------
			for(int i=1; i<n+1; i++) {
				int a = i;
				int b = Integer.parseInt(st.nextToken());
				union(a,b);
			}
            
            // -------------- 싸이클 찾기 --------------
			for(int k=1; k<n+1; k++) {
				if(ranks[k]!=0) {
					cycle++;
				}
			}
			sb.append(cycle+"\n");
		}
		System.out.println(sb.toString());
	}
	
	static int find(int x) {
		if(parents[x] == x) return x;
		
		int parent= find(parents[x]);
		return parent;
		
	}
	
	static void union(int x, int y) {
		x = find(x);
		y = find(y);
        
		// y가 부모 
		if(ranks[x] < ranks[y]) {   
			parents[x]= y;
			ranks[y]++; // 자식 추가 
			
		}else {
			parents[y] = x;  
			
			if(ranks[x]==ranks[y]) {
				ranks[x]++; // 자식 추가 
				
				// 길이가 1이상인 두 싸이클이 하나로 합쳐질 때  (x부모, y자식)
				if(ranks[y]!=0 && x!=y) { 
					ranks[x]++; 
					ranks[y]--;  
				}
			}
		}
	}
}

loosie999 2년 전 0

그냥 rank배열을 빼고 union-find로직으로만 해결했습니다.

union로직에서 x와 y의 parent가 같아지는 순간을 Cycle로 카운트하였더니 풀렸습니다!

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

문제

문제

출처

ICPC

싸이클을 Union-find으로 시도했는데 9%에서 막히네요 도와주세요!!

loosie999 2년 전 0

loosie999 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말