[BOJ 4195]友達ネットワーク(Java)
20428 ワード
質問する
ミンヘはソーシャルサイトで友達を作るのが好きな友達です.切手収集のように、ミンヘの趣味はソーシャルサイトで友达を集めることです.
あるサイトの友達関係が現れる順番に並べば、2人の友達ネットワークに何人いるかを判断するプログラムを作成することができます.
友人ネットワークとは,友人関係だけで移動できる関係である.
入力
最初の行は、テスト例の数を示します.各テストケースの最初の行には、100000を超えない友人関係の数Fが与えられる.次のF行は友達関係を作る順番に与えられます.友人関係は2人のユーザのIDからなり,アルファベットの大文字または小文字の長さが20未満の文字列のみである.
しゅつりょく
友達関係があるたびに、二人の友達ネットワークに何人いるかを知るプログラムを作成します.
方法
入力に応じて、ネットワークへの接続を続行する必要があります.また、ネットワークに何人いるかを引き続き理解する必要があります.
グラフで探ってみようネットワークの構成も簡単で、BFSまたはDFSを使用してネットワークに何人いるかを検索できます.ただし、入力条件によっては、友人の関係数は100000になる可能性があります.これは、ネットワークユーザの数を計算するためにナビゲーションを行うたびにタイムアウトが表示されることを意味します.
考えをグラフから集合に変換しましょう.関連セットを管理するためのデータ構造である分離セット(disjoint set)を思い出すかもしれません.
親に関連するネットワーク接続者の数を格納し、再接続時に親の場所(Union)のみを使用し、ナビゲーションするたびに使用する必要がないため、問題のニーズを満たすことができます.
少なくとも1つの
ソースコード
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
public class FriendNetwork {
static int index;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int testCase = Integer.parseInt(br.readLine());
for (int i = 0; i < testCase; i++) {
index = -1;
networking(sb, br);
}
System.out.println(sb);
br.close();
}
public static void networking(StringBuilder sb, BufferedReader br) throws IOException {
int f = Integer.parseInt(br.readLine());
HashMap<Integer, Integer> networkMemNumberMap = new HashMap<>(); // 네트워크 내부의 인원들을 담은 맵
HashMap<String, Integer> nameIndexMap = new HashMap<>(); // 이름 to 배열 index
int[] disjointSet = new int[f * 2];
// disjointSet init
for (int i = 0; i < f * 2; i++) {
disjointSet[i] = i;
networkMemNumberMap.put(i, 1);
}
for (int i = 0; i < f; i++) {
String[] input = br.readLine().split(" ");
int index1 = inputNameIndexMap(nameIndexMap, input[0]);
int index2 = inputNameIndexMap(nameIndexMap, input[1]);
sb.append(union(index1, index2, disjointSet, networkMemNumberMap)).append('\n');
}
}
public static int union(int i1, int i2, int[] disjointSet, Map<Integer, Integer> networkMemNumberMap) {
i1 = find(i1, disjointSet);
i2 = find(i2, disjointSet);
if (i1 != i2) {
int parent = Math.min(i1, i2);
int child = Math.max(i1, i2);
disjointSet[child] = parent;
networkMemNumberMap.put(parent, networkMemNumberMap.get(parent) + networkMemNumberMap.get(child));
networkMemNumberMap.remove(child);
return networkMemNumberMap.get(parent);
}
return networkMemNumberMap.get(i1);
}
public static int find(int start, int[] disjointSet) {
if (disjointSet[start] != start) {
return disjointSet[start] = find(disjointSet[start], disjointSet);
}
return start;
}
public static int inputNameIndexMap(Map<String, Integer> map, String name) {
if (!map.containsKey(name)) {
map.put(name, ++index);
}
return map.get(name);
}
}
結果
Reference
この問題について([BOJ 4195]友達ネットワーク(Java)), 我々は、より多くの情報をここで見つけました https://velog.io/@wotj7687/BOJ-4195-친구-네트워크-Javaテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol