https://www.acmicpc.net/problem/4195
4195번: 친구 네트워크
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진
www.acmicpc.net
분류 : 해싱, 최소 스패닝 트리, 강한 연결 요소, Disjoint-Set, 최대 독립 집합
더보기
import java.io.*;
import java.math.*;
import java.util.*;
class MyScanner {
BufferedReader br;
StringTokenizer st;
public MyScanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
}
public class Main {
static PrintWriter out;
// root[a] = b -> a의 부모는 b이다.
static int[] root = new int[200001];
static int[] count = new int[200001];
public static void main(String[] args) throws IOException {
MyScanner sc = new MyScanner();
out = new PrintWriter(new BufferedOutputStream(System.out));
int T = sc.nextInt();
for (int TC = 0; TC < T; TC++)
{
int cnt =1;
int F = sc.nextInt();
// root 초기화
for (int i = 1; i <= 2*F; i++)
{
root[i] = i;
count[i] = 1;
}
Map<String,Integer> map =new HashMap<String,Integer>();
for(int i=0;i<F;i++)
{
String str1 = sc.next();
String str2 = sc.next();
if(!map.containsKey(str1))
{
map.put(str1, cnt++);
}
if(!map.containsKey(str2))
{
map.put(str2, cnt++);
}
out.println(Union(map.get(str1),map.get(str2)));
}
}
out.flush();
}
private static int Union(int a, int b) {
a = Find(a);
b = Find(b);
if (a != b) {
root[a] = b;
count[b]+=count[a];
count[a] = 1;
}
return count[b];
}
private static int Find(int k) {
// 루트 노드 이면 return k
if (k == root[k])
return k;
// 그 외에는 자신의 루트를 찾으러 간다.
return root[k] = Find(root[k]);
}
}
Union-Find 알고리즘을 써야 하는 것은 알았다.
하지만 입력과 결합 부분을 어떻게 구현 해야 할지 잘 모르겠던 중 Map을 사용하라는 힌트와 대략적인 흐름을 스터디원에게서 들어 방향을 잡게 되었고 문제 해결 성공.
근데 혼자서 이걸 생각 해내라고 하면 글쎄.. 잘 모르겠다
'PS' 카테고리의 다른 글
[BOJ]10974번 : 모든 순열 (0) | 2017.03.29 |
---|---|
[BOJ]11657번 : 타임 머신 (0) | 2017.03.28 |
[BOJ]1976번 : 여행 가자 (0) | 2017.03.25 |
[BOJ]1717번 : 집합의 표현 (0) | 2017.03.25 |
[BOJ]1788번 : 피보나치 수의 확장 (0) | 2017.03.24 |