# HDELIVER - Editorial

EASY

### EXPLANATION

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)

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION**

Can be found here.

1 Like

can anyone explain how to apply DFS here… i know DFS algo already but not able to relate to the problem… plz help.

@hitesh091 combine graph coloring and dfs together…color the nodes of the same connected component with the same color(number)…hope this helps… 1 Like

i need to learn a lot… thanks kunal361… 1 Like

Him 'm getting tle for my solution. http://www.codechef.com/viewsolution/3114503 I’m developing in C#. Have tried to optimized as much as I can. Any pointers appreciated.

Simple application of Union find.

1 Like

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.PrintWriter;

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 {
BufferedWriter bw = new BufferedWriter(new PrintWriter(System.out));

for(int t=0;t<T;t++){
int n = Integer.parseInt(ln1); int m = Integer.parseInt(ln1);

DisjointSet D = new DisjointSet(n);

for(int i=0;i<m;i++){
int a = Integer.parseInt(ln2); int b = Integer.parseInt(ln2);
if(D.find(a)!=D.find(b)){
D.union(a, b);
}
}
for(int i=0;i<Q;i++){
int c = Integer.parseInt(ln3); int d = Integer.parseInt(ln3);
if(D.find(c)==D.find(d)){
bw.append("YO"+"\n");
}else{
bw.append("NO"+"\n");
}
}
}
bw.close();
}
``````

}

can we solve it by finding transpose of adjacency matrix ???

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.