[BOJ 4195]友達ネットワーク(Java)

質問する

ミンヘはソーシャルサイトで友達を作るのが好きな友達です.切手収集のように、ミンヘの趣味はソーシャルサイトで友达を集めることです.
あるサイトの友達関係が現れる順番に並べば、2人の友達ネットワークに何人いるかを判断するプログラムを作成することができます.
友人ネットワークとは,友人関係だけで移動できる関係である.

入力

最初の行は、テスト例の数を示します.各テストケースの最初の行には、100000を超えない友人関係の数Fが与えられる.次のF行は友達関係を作る順番に与えられます.友人関係は2人のユーザのIDからなり,アルファベットの大文字または小文字の長さが20未満の文字列のみである.

しゅつりょく

友達関係があるたびに、二人の友達ネットワークに何人いるかを知るプログラムを作成します.

方法

入力に応じて、ネットワークへの接続を続行する必要があります.また、ネットワークに何人いるかを引き続き理解する必要があります.

グラフで探ってみようネットワークの構成も簡単で、BFSまたはDFSを使用してネットワークに何人いるかを検索できます.ただし、入力条件によっては、友人の関係数は100000になる可能性があります.これは、ネットワークユーザの数を計算するためにナビゲーションを行うたびにタイムアウトが表示されることを意味します.

考えをグラフから集合に変換しましょう.関連セットを管理するためのデータ構造である分離セット(disjoint set)を思い出すかもしれません.

親に関連するネットワーク接続者の数を格納し、再接続時に親の場所(Union)のみを使用し、ナビゲーションするたびに使用する必要がないため、問題のニーズを満たすことができます.

に感謝
少なくとも1つの

テストキャビネットは、各テストでindexを初期化する必要があります.

を入力した友達の名前は異なるかもしれません.この場合、最大分離セットアレイサイズは2*fであることに注意してください.

ソースコード

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);
    }
}

結果