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。如果您找到一种方法来 aovid 字符串并改用 Integer，那将是一个优势。（例如 userId 而不是 userName

于 2013-03-09T19:30:13.683 回答