0

これは、私がここで尋ねた質問の続きです。
ノード (従業員) の総数と隣接リスト (従業員間の友情) を考えると、すべての接続されたコンポーネントを見つける必要があります
。以下は私のコードです -

    public class Main {
        static HashMap<String, Set<String>> friendShips;

        public static void main(String[] args) throws IOException {
            BufferedReader  in= new BufferedReader(new InputStreamReader(System.in));

                String dataLine = in.readLine();
                String[] lineParts = dataLine.split(" ");
                int employeeCount = Integer.parseInt(lineParts[0]);
                int friendShipCount = Integer.parseInt(lineParts[1]);
                friendShips = new HashMap<String, Set<String>>();
                for (int i = 0; i < friendShipCount; i++) {
                    String friendShipLine = in.readLine();
                    String[] friendParts = friendShipLine.split(" ");
                    mapFriends(friendParts[0], friendParts[1], friendShips);
                    mapFriends(friendParts[1], friendParts[0], friendShips);
                }
                Set<String> employees = new HashSet<String>();
                for (int i = 1; i <= employeeCount; i++) {
                    employees.add(Integer.toString(i));
                }
                Vector<Set<String>> friendBuckets = bucketizeEmployees(employees);
                System.out.println(friendBuckets.size());
        }

        public static void mapFriends(String friendA, String friendB, Map<String, Set<String>> friendsShipMap) {
            if (friendsShipMap.containsKey(friendA)) {
                friendsShipMap.get(friendA).add(friendB);
            } else {
                Set<String> friends = new HashSet<String>();
                friends.add(friendB);
                friendsShipMap.put(friendA, friends);
            }
        }

        public static Vector<Set<String>> bucketizeEmployees(Set<String> employees) {
            Vector<Set<String>> friendBuckets = new Vector<Set<String>>();
            while (!employees.isEmpty()) {
                String employee = getHeadElement(employees);
                Set<String> connectedEmployeesBucket = getConnectedFriends(employee);
                friendBuckets.add(connectedEmployeesBucket);
                employees.removeAll(connectedEmployeesBucket);
            }
            return friendBuckets;
        }

        private static Set<String> getConnectedFriends(String friend) {
            Set<String> connectedFriends = new HashSet<String>();
            connectedFriends.add(friend);
            Set<String> queuedFriends = new LinkedHashSet<String>();
            if (friendShips.get(friend) != null) {
                queuedFriends.addAll(friendShips.get(friend));
            }
            while (!queuedFriends.isEmpty()) {
                String poppedFriend = getHeadElement(queuedFriends);
                connectedFriends.add(poppedFriend);
                if (friendShips.containsKey(poppedFriend))
                    for (String directFriend : friendShips.get(poppedFriend)) {
                        if (!connectedFriends.contains(directFriend) && !queuedFriends.contains(directFriend)) {
                            queuedFriends.add(directFriend);
                        }
                    }
            }
            return connectedFriends;
        }

        private static String getHeadElement(Set<String> setFriends) {
            Iterator<String> iter = setFriends.iterator();
            String head = iter.next();
            iter.remove();
            return head;
        }
    }

次のスクリプトを使用してコードをテストしました。その結果は sdtIn として使用されます --

#!/bin/bash
echo "100000 100000"
for i in {1..100000}
do
    r1=$(( $RANDOM % 100000 ))
    r2=$(( $RANDOM % 100000 ))
    echo "$r1 $r2"
   done

私の答えが正しいことを（些細な入力の場合）確認できましたが、上記のスクリプトのように巨大な入力を試してみると、実行に時間がかかることがわかりました（〜20秒）。
実装で改善できることはありますか?

4

1 に答える 1

0

Vector同期されたクラスの使用は避けてください。ArrayList代わりに服用してください。文字列を回避し、代わりに整数を使用する方法を見つけた場合は、利点があります。(たとえば、userName の代わりに userId

于 2013-03-09T19:30:13.683 に答える