HDELIVER - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

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…:slight_smile:

1 Like

Him 'm getting tle for my solution. CodeChef: Practical coding for everyone 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.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
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 {
    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();
}

}

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.
Link: CodeChef: Practical coding for everyone

Please provide test cases for which my code fails.I am using bfs

Link: CodeChef: Practical coding for everyone

i need to learn a lot… thanks kunal361… :slight_smile:

1 Like