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

    結果