Hi,
I am currently attempting the problem “Home delivery” from the March long contest. As soon as I saw it, I knew that all I needed was to use a Union-Find data structure. My code is very simple and straight forward, yet I am getting TLE. ( I have implemented both path-compression as well as union-by-rank in my union-find data structure )
I would be very grateful if anyone could suggest improvements to my code. Thank you
CODE :
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
/*
Implements DisjointSet data structure using both Union by Rank as well
as Path Compression
*/
class DisjointSet
{
private int[] parent;
private int[] rank;
private int size;
public DisjointSet( int n )
{
size = n;
parent = new int[ n ];
Arrays.fill( parent, -1 );
rank = new int[ n ];
Arrays.fill( rank, -1 );
}
public void makeSet( int x )
{
parent[ x ] = x;
rank[ x ] = 0;
}
public int findRoot( int x )
{
if( parent[x] != x )
parent[ x ] = findRoot( parent[x]);
return parent[x];
}
public void Union( int x, int y )
{
int root1 = findRoot( x ) ;
int root2 = findRoot( y );
if( root1 != root2)
Link( root1, root2 );
}
private void Link( int x, int y )
{
if( rank[ x ] < rank[ y ]) // Make y x's parent
{
parent[ x ] = y;
}
else if( rank[ x ] > rank[ y ])
{
parent[ y ] = x;
}
else
{
parent[ x ] = y;
rank[ y ]++;
}
}
}
public class Main
{
static int n, m;
public static void main( String[] args ) throws IOException
{
BufferedReader br = new BufferedReader( new InputStreamReader( System.in ));
int T = Integer.parseInt( br.readLine() );
StringTokenizer tok;
String s;
while( T-- > 0 )
{
s = br.readLine();
tok = new StringTokenizer( s );
n = Integer.parseInt( tok.nextToken() );
m = Integer.parseInt( tok.nextToken() );
DisjointSet d = new DisjointSet( n );
for( int i=0; i<n; i++ )
d.makeSet( i );
for( int i=0; i<m; i++ )
{
s = br.readLine();
tok = new StringTokenizer( s );
int a = Integer.parseInt( tok.nextToken() );
int b = Integer.parseInt( tok.nextToken() );
if( a==b )
continue;
d.Union(a, b);
}
int q = Integer.parseInt( br.readLine() );
for( int i=0; i<q; i++ )
{
s = br.readLine();
tok = new StringTokenizer( s );
int a = Integer.parseInt( tok.nextToken() );
int b = Integer.parseInt( tok.nextToken() );
if( d.findRoot(a) == d.findRoot(b))
System.out.println("YO");
else
System.out.println("NO");
}
}
}
}