1

我正在解决这个挑战：https ://open.kattis.com/problems/virtualfriends

我的解决方案似乎有效，但 kattis 的测试用例运行速度太慢，所以我想知道如何提高代码效率。我正在使用定制的联合查找结构来执行此操作，将“朋友”存储到树形图中以供参考。

import java.util.*;
public class virtualfriends {

    public static void main(String[] args) {


        Scanner scan = new Scanner(System.in);
        int testcases = scan.nextInt();

        scan.nextLine();

        for (int i= 0; i < testcases; i++) {
            int numFriendships = scan.nextInt();
            scan.nextLine();
            TreeMap<String , Integer> map = new TreeMap<String , Integer>(); 
            int cnt = 0;
            UF unionFind = new UF(50000);
            for (int j = 0; j < numFriendships; j++)
            {

                String p1 = scan.next();
                String p2 = scan.next();
                if (!map.containsKey(p1)) map.put(p1, cnt++);
                if (!map.containsKey(p2)) map.put(p2, cnt++);
                unionFind.unify(map.get(p1), map.get(p2));
                System.out.printf("%d\n", unionFind.getSetSize(map.get(p2)));
            }
        }
    }

    static class UF{
        private int[] id, setSize;
        private int numSets;

        public UF(int size) {
            id = new int[size] ;
            setSize = new int[size];
            numSets = size;
            for(int i = 0 ; i < size ; ++i) {
                id[i] = i;
                setSize[i] = 1;
            }
        }

        int find(int i ) 
        {
            int root = i;
            while (root != id[root]) {
                root = id[root];
            }
            while (i != root) {
                int newp = id[i];
                id[i] = root;
                i = newp;
            }
            return root;
        }

        boolean isConnected(int i , int j) {
            return find(i) == find(j);
        }

        int getNumSets() {
            return numSets;
        }

        int getSetSize(int i) {
            return setSize[find(i)];
        }

        boolean isSameSet(int i, int j) {
            return find(i) == find(j);
        }

        void unify(int i, int j)
        {
            int root1 = find(i);
            int root2 = find(j);
            if (root1 == root2) return;

            if (setSize[root1] < setSize[root2]) 
            {
                setSize[root2] += setSize[root1];
                id[root1] = root2;
            } else {
                setSize[root1] += setSize[root2];
                id[root2] = root1;
            }
            numSets--;
        }

    }

}
4

0 回答 0