Restating the problem in terms of Graph Theory, we’re given a set of edges, and we’ve to identify if two given query points are connected via these edges or not. One could do a depth first search (DFS) from one of the vertices and monitor if the other vertex is visited or not, but time limits were set in such a way that it was difficult to get accepted if one is doing a dfs at each query. Instead, after only one DFS, we could store all the connected components. After that each query can be answered in constant time. Look at tester’s solution.
Alternate approach could be to build union-find data structure over the graph. As before, each query could now be answered in constant time. Look at setter’s solution for this approach. So in both the solutions, desired time complexity was O(E +V + Q)
class DisjointSet{
private int[] p; //The parent Link
private int[] r; //The rank Link
private int count;
public DisjointSet(int n){
this.count=n;
p = new int[n];
r = new int[n];
for(int i=0;i<n;i++){
p[i]=i;
r[i]=0;
}
}
/**
* It is only called when x and y are in different sets
* @param x
* @param y
*/
public void union(int x, int y){
x=find(x);
y=find(y);
if(x==y) return;//disjoint setz allowed
if(r[x]>r[y]){
p[y]=x;
}
else{
p[x]=y;
if(r[x]==r[y]){
r[y]+=1;
}
}
}
public void setparent(int x,int y){
this.p[x]=y;
}
public int[] getparent(){
return this.p;
}
public int find(int x){
if(x==p[x]) return x;
int root = find(p[x]);
p[x]=root;
return root;
}
}
public class HDelivery {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new PrintWriter(System.out));
int T = Integer.parseInt(br.readLine());
for(int t=0;t<T;t++){
String[] ln1 = br.readLine().split(" ");
int n = Integer.parseInt(ln1[0]); int m = Integer.parseInt(ln1[1]);
DisjointSet D = new DisjointSet(n);
for(int i=0;i<m;i++){
String[] ln2 = br.readLine().split(" ");
int a = Integer.parseInt(ln2[0]); int b = Integer.parseInt(ln2[1]);
if(D.find(a)!=D.find(b)){
D.union(a, b);
}
}
int Q = Integer.parseInt(br.readLine());
for(int i=0;i<Q;i++){
String[] ln3 = br.readLine().split(" ");
int c = Integer.parseInt(ln3[0]); int d = Integer.parseInt(ln3[1]);
if(D.find(c)==D.find(d)){
bw.append("YO"+"\n");
}else{
bw.append("NO"+"\n");
}
}
}
bw.close();
}
I recently learned Union find… I applied the algorithm in this problem according to the tutorial… But I have not done path compression. Please can anybody have a look at my code at let me know why am i getting a TLE. What changes should I make in my code? Thank you.
Link: https://www.codechef.com/viewsolution/8235186
