Finding the size of the largest connected component in a graph

Question

Given this question, which simply can be explained as follows:

Given the number of nodes and the number of edges in a graph, find the size of the largest connected component of the graph. If this number is K, then return the Kth prime number.

I used two approaches here:

1. BFS: I did a BFS over all the unvisited nodes, which while working, also counts the visited nodes, in order to obtain the component's size. The maximum of these sizes is returned.
2. Disjoint Sets: I made sets of all the nodes, and did a unionSet procedure in order to join the nodes, into a single set. While this happens, we can maintain the total number of nodes in each set, for each set representative (or head).

For finding the Kth prime, I used the Sieve of Eratosthenes, for the 4,00,000 limit (as the test cases don't really ask above that). This, in my opinion is not the bottleneck, and is done only once for all the test cases.

Both of these methods worked correctly, but took more than expected. Both of these take O(edges) time. I don't think that a lower asymptotic bound is possible for this case, as we have to see all the edges once.

Rather, I think the code can improve upon constants.

Code for the first method:

import java.util.* ;
import java.io.BufferedReader ;
import java.io.InputStreamReader ;

public class SantaBanta
{
    public static void main(String args[]) throws Exception
    {
        BufferedReader bro = new BufferedReader(new InputStreamReader(System.in)) ;
        int T = Integer.parseInt(bro.readLine()); 
        HashMap<Integer,Integer> H = primes() ;
        for(int t=0;t<T;t++)
        {
            String[] S = bro.readLine().split(" ") ;
            int n = Integer.parseInt(S[0]) ;
            int m = Integer.parseInt(S[1]) ;
            ArrayList<ArrayList<Integer>> M = new ArrayList<ArrayList<Integer>>() ;
            for(int i=0;i<=n;i++)
                M.add(new ArrayList<Integer>()) ;
            for(int i=0;i<m;i++)
            {
                S = bro.readLine().split(" ") ;
                int a = Integer.parseInt(S[0]) ;
                int b = Integer.parseInt(S[1]) ;
                M.get(a).add(b) ;
                M.get(b).add(a) ;
            }
            int num = solve(M) ;
            System.out.println(m==0?"-1":H.get(num)) ;
        }
    }
    static int solve(ArrayList<ArrayList<Integer>> M)
    {//will do a bfs, to find the largest connected component
        boolean[] visited = new boolean[M.size()] ;
        int max_size = Integer.MIN_VALUE ;
        for(int i=0;i<M.size();i++)
        {

            if(!visited[i])
            {
                int size = 0 ;
                ArrayDeque<Integer> DQ = new ArrayDeque<Integer>() ;
                // int src = i ;
                DQ.add(i) ;
                while(!DQ.isEmpty())
                {

                    int temp = DQ.poll() ;
                    if(visited[temp]) continue ;
                    visited[temp] = true ;
                    size++ ;
                    for(int j=0;j<M.get(temp).size();j++)
                    {
                        int val = M.get(temp).get(j) ;
                        if(!visited[val])
                            DQ.add(val) ;
                    }
                }
                if(size>max_size)
                    max_size = size==1?max_size:size ;
            }
        }
        return max_size ;

    }
    static HashMap<Integer,Integer> primes()
    {//assuming the maximum prime number needed will not exceed 1e5 
        int n=400000 ;
        HashMap<Integer,Integer> H = new HashMap<Integer,Integer>() ;
        boolean[] notPrime = new boolean[n+1] ;//A false value means that the index i is prime.
        for(int i=2;i<notPrime.length;i++)
        {//Sieve of Eratosthenes
            if(!notPrime[i])
            {
                for(int j=2*i;j<n;j+=i)
                {
                    notPrime[j] = true ;
                }
            }
        }
        int count = 1 ;
        for(int i=2;i<notPrime.length;i++)
        {
            if(!notPrime[i]) 
                H.put(count++,i) ;
        }
        return H ;
    }

}

Here is the code for the second approach:

import java.util.*;
import java.io.BufferedReader ;
import java.io.InputStreamReader ;

public class SantaBanta2
{
    private static final boolean debug = true ;
    public static void main(String args[]) throws Exception
    {
        BufferedReader bro = new BufferedReader(new InputStreamReader(System.in)) ;
        int T = Integer.parseInt(bro.readLine()); 
        HashMap<Integer,Integer> H = primes() ;
        for(int t=0;t<T;t++)
        {
            String[] S = bro.readLine().split(" ") ;
            int n = Integer.parseInt(S[0]) ;
            int m = Integer.parseInt(S[1]) ;
            UnionFind U = new UnionFind(n+1) ;
            for(int i=0;i<m;i++)
            {
                S = bro.readLine().split(" ") ;
                int a = Integer.parseInt(S[0]) ;
                int b = Integer.parseInt(S[1]) ;
                U.unionSet(a,b) ;
            }
            int max_size = 0 ;
            for(int i=0;i<U.setSize.length;i++)
            {

                if(U.setSize[i]>max_size) max_size = U.setSize[i] ;
            }
            if(debug) 
            {
                System.out.println("max_size :"+max_size) ;
                // arrayPrinter(U.setSize) ;
            }
            System.out.println(max_size==0?"-1":H.get(max_size)) ;

        }
    }
    static void arrayPrinter(int[] A)
    {
        for(int a:A) System.out.print(a+" ") ;
        System.out.println() ;
    }
    static HashMap<Integer,Integer> primes()
    {//assuming the maximum prime number needed will not exceed 1e5 
        int n=400000 ;
        HashMap<Integer,Integer> H = new HashMap<Integer,Integer>() ;
        boolean[] notPrime = new boolean[n+1] ;//A false value means that the index i is prime.
        for(int i=2;i<notPrime.length;i++)
        {//Sieve of Eratosthenes
            if(!notPrime[i])
            {
                for(int j=2*i;j<n;j+=i)
                {
                    notPrime[j] = true ;
                }
            }
        }
        int count = 1 ;
        for(int i=2;i<notPrime.length;i++)
        {
            if(!notPrime[i]) 
                H.put(count++,i) ;
        }
        return H ;
    }
}
class UnionFind
{
    int[] p,rank,setSize ;
    UnionFind(int N)
    {
        p = new int[N] ;
        rank = new int[N] ;
        setSize = new int[N] ;
        Arrays.fill(setSize,1) ;
        setSize[0] = 0 ;
        for(int i=0;i<N;i++) p[i] = i ;

    }
    int findSet(int i) 
    {
        return (p[i]==i)?i:(p[i] = findSet(p[i])) ;
    }
    boolean isSameSet(int i,int j)
    {
        return findSet(i)==findSet(j) ;
    }
    void unionSet(int i,int j)
    {
        if(!isSameSet(i,j))
        {
            int x = findSet(i),y = findSet(j) ;
            if(rank[x]>rank[y]) 
            {
                p[y] =x ;
                setSize[x]+=setSize[y] ;
                setSize[y] = 0 ;

            }
            else
            {
                p[x] = y ;
                if(rank[x]==rank[y]) rank[y]++ ;
                setSize[y]+=setSize[x] ;
                setSize[x] = 0 ;
            }
        }
    }
}

Any suggestions for improving the code are requested.

Answer 1

• About the first approach:

  • I would initialize max_size to 0 instead of Integer.MIN_VALUE, because if the graph does not contain any nodes, the for loop over M will never be executed, and the size of the largest connected component in an empty graph is 0.

  • I would replace this:

    if (visited[temp]) continue;
    visited[temp] = true;
    //...
    

    with this:

    if (!visited[temp]) {
        visited[temp] = true;
        //...
    }
    

    Not because I'm dogmatically against break and continue, but I think that, in general, code is easier to read if the control flow is apparent from the code's structure alone. Of course, there might always be exceptions, but I don't think your continue statement makes the code easier to read than the above alternative without a continue statement. Incidentally, you already did exactly what I suggested in the outer for loop where you check if i has already been visited.

  • Here:

    if(size>max_size)
        max_size = size==1?max_size:size ;
    

    Why do you make a special case for size == 1? A node with no edges is also a component of the graph, and if the graph only contains nodes but no edges, then the largest connected component will have the size 1.

  • You can replace this for loop:

    for(int j=0;j<M.get(temp).size();j++)
    {
        int val = M.get(temp).get(j) ;
        if(!visited[val])
            DQ.add(val) ;
    }
    

    with an enhanced for loop, eliminating the need for an additional local variable (j).

  • If you make DQ a Set instead of a Deque, then you wouldn't need to check whether the next node that you retrieve from DQ has already been visited. In fact, a Set might be more appropriate here in general, because a Deque implies a specific processing order, but it actually doesn't matter in which order you visit the nodes, as long as the nodes you visit are connected to the starting node, directly or indirectly. Of course, a Set doesn't come with such an elegant way as Deque.poll() to retrieve and remove an element at the same time, so you would have to create an iterator and use it to return an arbitrary element from the set.

• About the second approach:

  • You might be interested to know that there's a method Arrays.toString(int[]), so you don't need to write your own arrayPrinter(int[]) method.

  • Making the size of the arrays one element larger than the number of nodes just so you can refer to the nodes using one-based indexes is unelegant and confusing, because it makes the first element of every array completely meaningless. I think it would be less confusing if you simply subtracted 1 from the original indexes before passing them to UnionFind, because that way, the arrays don't store more data than they need to.

• About the method primes():

  • It is sufficient to initialize j to i*i instead of 2*i, because every multiple of i with a prime factor less than i will already have been marked as composite when the value of i was that prime factor. You'd only somehow have to make sure that i*i does not cause an overflow (but on the other hand, 2*i could cause an overflow as well if n is sufficiently large). You could try using Math.multiplyExact(int, int) for the initialization and Math.addExact(int, int) for the increment, and swallow any potentially thrown ArithmeticException to terminate the inner for loop.

  • I would make n a method parameter instead of hard coding it into the method. After all, it's not for the method to foresee what you want to do with the result returned by it.

  • Instead of returning a HashMap<Integer, Integer> where the keys only act as consecutive indexes, why don't you simply return a List<Integer>, where the association of elements with consecutive indexes is inherent to the data structure?

A final remark: It is usually not necessary to declare variables or method parameters as interface implementations (e.g. ArrayList, HashSet) rather than interfaces (e.g. List, Set). For example, the solve method in your first approach only depends on the functionality of the interface List and not on how this interface is implemented, so it might as well accept any List<List<Integer>> instead of only an ArrayList<ArrayList<Integer>>.

Answer 2

For finding the Kth prime, I used the Sieve of Eratosthenes, for the 4,00,000 limit (as the test cases don't really ask above that). This, in my opinion is not the bottleneck, and is done only once for all the test cases.

Have you profiled? Bottlenecks are often surprising.

I would have thought it worthwhile to accumulate the values of k first, so you know exactly how many primes you need, and then to add an early exit to the sieve when you've found enough.

---

            ArrayList<ArrayList<Integer>> M = new ArrayList<ArrayList<Integer>>() ;

I have a lot to say about this line.

1. Code to the interface, not the implementation. That would make it

               List<List<Integer>> M = new ArrayList<List<Integer>>() ;
   

2. If you're using a recent Java compiler, you can omit some boiler plate when creating an instance of a generic class.

               List<List<Integer>> M = new ArrayList<>() ;
   

3. Why is the inner type List<>? As far as I can tell the order is irrelevant, so I would think that Set<> made more sense.

4. M? Names should communicate meaning. My best guess is that it's short for matrix, but you don't actually have a matrix here. Options for better names include adjacencyLists and neighbours. Most of the other variable names are also too cryptic IMO.

---

Java 5 introduced java.util.Scanner, which would make the data input much nicer to read.

---

The code is pretty consistent with whitespace, which is good, but it seems to follow a style document which makes some unusual decisions. In particular, I would highlight the ternary operator ? : and the traditional for(A; B; C) as two places where I would find the readability improved by the addition of whitespace.