백준 4195 - 친구 네트워크

백준 4195 - 친구 네트워크

https://www.acmicpc.net/problem/4195

★ 풀이

HashMap을 통해서 친구의 이름마다 고유의 INDEX 값을 부여한다. 이제 유니온 파인드를 활용해서 병합을 처리해주고, 이 병합을 처리해 줄 때 추가적으로 네트워크에 몇 명이 있는지를 구하기 위해 count 배열을 활용해서 처리해 준다. 각각의 집합의 루트 노드에 자신이 속한 집합의 전체 노드 수를 적어두고.. 병합을 할 때에는 큰 집합 루트 노드에서 작은 집합 루트 노드를 흡수하는 형식으로 처리해 준다.

★ 소스 코드

import java.io.*; import java.util.*; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static int parent[],rank[]; static HashMap hm; public static void main(String[] args) throws IOException { int T = Integer.parseInt(br.readLine()); StringBuilder sb = new StringBuilder(); while(T-->0) { int n = Integer.parseInt(br.readLine()); int idx = 1; hm = new HashMap<>(); parent = new int[2*n+1]; rank = new int[2*n+1]; count = new int[2*n+1]; for(int i = 1; i<=2*n; i++) { parent[i] = i; count[i] = 1; } for(int i = 0; i

"); } } System.out.println(sb); } static int count[]; static void union(int a, int b) { a = find(a); b = find(b); if(a == b) return; if(rank[a] > rank[b]) { int tmp = a; a = b; b = tmp; } count[b] += count[a]; parent[a] = b; if(rank[a] == rank[b]) rank[a]++; } static int find(int u) { if(parent[u] == u) return u; return parent[u] = find(parent[u]); } }

from http://sweet-smell.tistory.com/138 by ccl(A) rewrite - 2021-12-06 17:01:06