[伯俊]4195号友人ネットワーク/Java,Python


Baekjoon Online Judge


algorithm practice


-問題を逐次解く


29.ユニコーン


union find(またはdisjointセット、反発セット、...)資料の構造を学びましょう.
Java/Python

3.友人ネットワーク


4195号
集合サイズを求める機能をUnion Findに入れる問題

今回の質問は、あるサイトの友達関係が出てくる順に出した場合、2人の友達ネットワークに何人いるかということです.ここで,友人ネットワークとは,友人関係だけで移動できる関係である.
union関数を使用してparentを独自に初期化し、関数findと集約演算を使用して親を検索し、親が同じ親を持つようにします.
  • Java
  • import java.io.*;
    import java.util.*;
    
    public class Main {
    	static int[] parent;
    	static int[] cnt;
    
    	public static void main(String[] args) throws Exception {
    		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    		StringTokenizer st;
    		StringBuilder sb = new StringBuilder();
    
    		int T = Integer.parseInt(br.readLine());
    
    		while (T-- > 0) {
    			int F = Integer.parseInt(br.readLine());
    
    			parent = new int[F * 2];
    			cnt = new int[F * 2];
    
    			for (int i = 0; i < F * 2; i++) {
    				parent[i] = i;
    				cnt[i] = 1;
    			}
    
    			int idx = 0;
    			HashMap<String, Integer> map = new HashMap<>();
    
    			for (int i = 0; i < F; i++) {
    				st = new StringTokenizer(br.readLine());
    				String f1 = st.nextToken();
    				String f2 = st.nextToken();
    
    				if (!map.containsKey(f1)) {
    					map.put(f1, idx++);
    				}
    
    				if (!map.containsKey(f2)) {
    					map.put(f2, idx++);
    				}
    				sb.append(union(map.get(f1), map.get(f2)) + "\n");
    			}
    		}
    
    		bw.write(sb.toString());
    		bw.flush();
    		bw.close();
    		br.close();
    	}
    
    	// x의 부모 찾기
    	public static int find(int x) {
    		if (x == parent[x])
    			return x;
    
    		return parent[x] = find(parent[x]);
    	}
    
    	// y 부모를 x 부모로 치환하기 (x > y 일 경우 반대)
    	public static int union(int x, int y) {
    		x = find(x);
    		y = find(y);
    
    		// 항상 x < y인 값이 들어온다고 가정
    		if (x != y) {
    			parent[y] = x;
    			cnt[x] += cnt[y]; // y에 있던 층의 개수를 더해 줌.
    
    			cnt[y] = 1;
    		}
    		return cnt[x];
    	}
    }
  • Python
  • import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    
    def find(x):
        if x == parent[x]:
            return x
        parent[x] = find(parent[x]) # 부모 테이블 갱신
        return parent[x]
    
    def union(x,y):
        x = find(x)
        y = find(y)
    
        if x != y:
            parent[y] = x
            number[x] += number[y]
        print(number[x])
    
    test_case = int(input())
    
    for _ in range(test_case):
        parent = {} # dictionary
        number = {}
    
        f = int(input())
    
        for _ in range(f):
            f1,f2 = input().split()
            
            if f1 not in parent:
                parent[f1] = f1
                number[f1] = 1
            if f2 not in parent:
                parent[f2] = f2
                number[f2] = 1
            
            union (f1,f2)