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:
- 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.
- 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.