[伯俊]4195号友人ネットワーク/Java,Python
Baekjoon Online Judge
algorithm practice
-問題を逐次解く
29.ユニコーン
union find(またはdisjointセット、反発セット、...)資料の構造を学びましょう.
Java/Python
3.友人ネットワーク
4195号
集合サイズを求める機能をUnion Findに入れる問題
今回の質問は、あるサイトの友達関係が出てくる順に出した場合、2人の友達ネットワークに何人いるかということです.ここで,友人ネットワークとは,友人関係だけで移動できる関係である.
union関数を使用してparentを独自に初期化し、関数findと集約演算を使用して親を検索し、親が同じ親を持つようにします.
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];
}
}
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)
Reference
この問題について([伯俊]4195号友人ネットワーク/Java,Python), 我々は、より多くの情報をここで見つけました https://velog.io/@jini_eun/백준-4195번-친구-네트워크-Java-Pythonテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol