Reducing time complexity of undirected graph

Question

I have a undirected graph that represents user connections in a social media like Facebook. There are N nodes that starts from 1 to N Edges are represented by arrays from and to. Task array represents the node number for which I am interested to find the connections for that node (i.e user in social media).

Example:

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

Answer:

[4,4,1]

Explanation:

The graph looks like this:

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]

So result is [4,4,1]

Constraints:

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

This is a hackerrank question. My code is failing for 8 test cases out of 15 saying time out errors for large inputs.

Here is my code:

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;
}

I tried recursive approach also, still same issue , I am getting time out errors for large input size values.

How to reduce time complexity of this code.

Answer 1

When the input is larger, the BFS algorithm will be run over the same graph component over and over again, always to derive the same node count. This is a pity. One solution is to repeat the BFS immediately a second time, but then mark the visited nodes with the count that you found in the first phase. Whenever BFS is about to be called on a node that already has that mark, you can just return that and skip the BFS execution.

Alternative: Disjoint Sets

Instead of creating a graph, you could create a disjoint-set data structure. This structure is aware of the component a node is part of, and can keep track of the component's size while the structure is populated. It does not precisely track all the edges of the graph, but will only maintain one link per node, just to track component-membership.

There are several alternative algorithms to merge two components. One is "union by size", which seems appropriate here, because we are interested in the size.

Here is a possible implementation of a DisjointSets class:

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;
    }
}

The solve function can then be:

    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;
    }