查找网络中的最大用户数

Question

我有m行，其中x和y值用空格分隔，表示用户id。这就像用户x在Facebook或Instagram上跟踪用户y一样。现在如果我们有一对z和y，那么由于z跟踪y，因为我们已经有一个组[x，y]，那么我们可以合并z形成[x，y，z]

例：

1 2
3 4
5 6
1 5

我们可以有以下组：

[1 2 5 6]和[3 4]，最大组[1，2，5，6]的长度为4将是答案。

这是我对此的方法：

public int process(int m, int[][] arr) {
    List<Set<Integer>> list = new ArrayList<>();
    
    int ans = 0;
    for(int i=0; i<m; i++) {
        int x = arr[i][0], y = arr[i][1];
        if(j ==0) {
            Set<Integer> set = new HashSet<>();
            list.add(set);
            set.add(x);
            set.add(y);
            ans = 2;
            continue;
        }
        boolean found = false;
        for(Set<Integer> set : list) {
            if(set.contains(x) || set.contains(y)) {
                set.add(x);
                set.add(y);
                ans = Math.max(ans, set.size());
                found = true;
                break;
            }
        }
        if(!found) {
            Set<Integer> set = new HashSet<>();
            list.add(set);
            set.add(x);
            set.add(y);
        }
    }
    return ans;
} 

我的方法本身是错误的，因为我生成的列表没有正确分组元素。如何解决这个问题。此外，输入阵列长度可以达到100000，因此需要以较少的时间复杂度来解决这个问题。

约束条件:

x and y can range from 1 to 10^5
aray length can be up to 10^6

Answer 1

您可以使用不相交集，从大小为 1 的每个组开始，并在合并时组合大小。

java prettyprint-override">public int process(int m, int[][] arr) {
    class DS {
        static int[] p = new int[100001];
        static int[] size = new int[100001];
        static int find(int x) {
            return x == p[x] ? x : (p[x] = find(p[x]));
        }
        static int merge(int x, int y) {
            int rx = find(x), ry = find(y);
            if (rx != ry) {
                p[rx] = ry;
                size[ry] += size[rx];
            }
            return size[ry];
        }
        static void init() {
            for (int i = 0; i < p.length; i++) {
                p[i] = i;
                size[i] = 1;
            }
        }
    }
    DS.init();
    int ans = 0;
    for (int[] pair: arr) 
        ans = Math.max(ans, DS.merge(pair[0], pair[1]));
    return ans;
}