降低无向图的时间复杂度

Question

我有一个无向图，表示 Facebook 等社交媒体中的用户连接。 有N个节点，从1到N 边由数组 from 和 to 表示。 任务数组表示我有兴趣查找该节点（即社交媒体中的用户）的连接的节点号。

示例：

N = 5
From = [2,2,1,1]
To = [1,3,3,4]
Task = [4,2,5]

答案：

[4,4,1]

说明：

图表如下所示：

Now for Task [4,2,5]

4 -> [1,2,3,4] The node 4 has these connections 
2 -> [1,2,3,4] The node 2 has these connections 
5 -> [5]

所以结果是[4,4,1]

限制：

N=2 to 10^5
size of arrays from, 'to', and tasks is 2 to 10^5

这是一个黑客级别的问题。我的代码在 15 个测试用例中有 8 个失败，表示大输入出现超时错误。

这是我的代码：

public static List<Integer> solve(int N, List<Integer> from, List<Integer> to, List<Integer> tasks) {
    int n = from.size();
    // Create the graph
    Map<Integer, Set<Integer>> map = new HashMap<>();
    for(int i=0; i<n; i++) {
        int key1 = from.get(i);
        int key2 = to.get(i);
        
        Set<Integer> value = map.getOrDefault(key1, new HashSet<>());
        value.add(key2);
        map.put(key1, value);
        
        value = map.getOrDefault(key2, new HashSet<>());
        value.add(key1);
        map.put(key2, value);       
    }
    List<Integer> result = new ArrayList<>();
    for(int node: tasks) {
        result.add(bfs(map, node));
    }
    return result;
}
    // Solve using breadth first search approach
public static int bfs(Map<Integer, Set<Integer>> map, int node) {
    Set<Integer> visited = new HashSet<>();
    Queue<Integer> q = new LinkedList<>();
    int count = 0;
    visited.add(node);
    q.add(node);
    while(!q.isEmpty()) {
        node = q.poll();
        count++;
        Set<Integer> val = map.get(node);
        if(val != null) {
            for(int next : val) {
                if(visited.add(next)) {
                    q.add(next);
                }
            }
        }
    }
    return count;
}

我也尝试了递归方法，仍然是同样的问题，对于大输入大小值，我遇到超时错误。

如何降低这段代码的时间复杂度。

Answer 1

当输入较大时，BFS 算法将一遍又一遍地在同一图组件上运行，始终得出相同的节点数。这是一个遗憾。

您可以创建一个不相交集，而不是创建图。 不相交集知道节点所属的组件，并且可以在填充结构时跟踪组件的大小。

有几种替代算法可以合并两个组件。一次是“按大小联合”，这在这里似乎很合适，因为我们对大小感兴趣。

这是

DisjointSets

类的可能实现：

import java.util.*;

class DisjointSets<T> {
    private class Node {
        Node parent;
        int size;
        T key;

        Node(T key) {
            this.key = key;
            this.size = 1;  // The node starts as its own component
            this.parent = this;
        }
    }

    Map<T, Node> nodes = new HashMap<>();

    private Node find(T key) {
        Node node = nodes.computeIfAbsent(key, Node::new);
        while (node.parent != node) {
            node = node.parent = node.parent.parent; // Path halving
        }
        return node;
    }

    public void union(T keyA, T keyB) {
        Node nodeA = find(keyA);
        Node nodeB = find(keyB);
        if (nodeA == nodeB) return; // Already in same set
        if (nodeA.size < nodeB.size) {
            nodeA.parent = nodeB;
            nodeB.size += nodeA.size;
        } else {
            nodeB.parent = nodeA;
            nodeA.size += nodeB.size;
        }
    }

    public int size(T key) {
        return find(key).size;
    }
}

solve

函数可以是：

    public static List<Integer> solve(int N, List<Integer> from, List<Integer> to, List<Integer> tasks) {
        int n = from.size();
        DisjointSets<Integer> set = new DisjointSets<>();
        for (int i = 0; i < n; i++) {
            set.union(from.get(i), to.get(i)); // populate disjoint sets
        }
        List<Integer> result = new ArrayList<>();
        for (int node : tasks) {
            result.add(set.size(node));
        }
        return result;
    }