HackeEarth Flipkart’s Drone

HackeEarth Flipkart’s Drone : After listening to the news of testing of Delivery Drone
But this was only possible if two of the shipping addresses had “V1-type” road connecting them(V1-type roads are the fastest in the city). So, Sachin and Binny ask you for a little help. They want you to tell them if they could send two orders together for two given locations or not.
Read Question at :http://www.hackerearth.com/problem/algorithm/sachins-drones/Input
First line of the input contains an integer T, denoting the number of test cases for your problem. Then T test cases follow. First line of each test case contains two integers N and M, denoting number of shipping addresses and the number of V1-type roads. Then M lines follow each containing two space separated integers A and B, denoting that there is a V1-type road between locations A and B. Assume that locations are indexed by numbers from 0 to N-1.
Next line contains an integer Q denoting the number of queries made by Flipkart founders to you. Each of the next Q lines contain two integers X and Y. For each query you have to find out if orders meant for shipping addresses X and Y can be sent together or not.
Note that there might be multiple V1-type roads between same pair of locations, also there might be a V1-type road that links a location to itself.Output
For each test case print Q lines – one for each query. Output “YES” if the orders are to be delivered together and “NO” otherwise.

Constraints
1 <= T <= 200
1 <= N <= 200
1 <= M <= 3000
0 <= A, B, X, Y <= N-1
1 <= Q <= 10000

Sample Input (Plaintext Link)
1
4 2
0 1
1 2
3
0 2
0 3
2 1

Sample Output (Plaintext Link)
YES
NO
YES

Solution 1 : Graph Based Solution (DFS)

#include <iostream>
#include <list>

using namespace std;

#define gc getchar_unlocked
#define pc putchar_unlocked
inline int scan(){register int n=0,c=gc();while(c<'0'||c>'9')c=gc();while(c<='9'&&c>='0')n=(n<<1)+(n<<3)+c-'0',c=gc();return n;} 

class Graph
{
    int V;    // No. of vertices
    list<int> *adj;    // Pointer to an array containing adjacency lists
    int DFSUtil(int a ,int b, bool visited[]);  // A function used by DFS
public:
    Graph(int V);   // Constructor
    void addEdge(int a ,int b);   // function to add an edge to graph
    int DFS(int a ,int b);    // DFS traversal of the vertices reachable from v
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w);
    adj[w].push_back(v);
}

int Graph::DFSUtil(int a, int b, bool visited[])
{
    // Mark the current node as visited and print it
    int ret=0;
    visited[a] = true;
    //out <<"Nodes= " << a <<"n";
  if(a == b) return 1;
    // Recur for all the vertices adjacent to this vertex
    list<int>::iterator i;
    for(i = adj[a].begin(); i != adj[a].end(); ++i)
        if(!visited[*i]){
            ret = DFSUtil(*i,b, visited);
            return ret;
            }

}
int Graph::DFS(int a, int b)
{
    // Mark all the vertices as not visited
    bool *visited = new bool[V];
    int ret=0;
    for(int i = 0; i < V; i++)
        visited[i] = false;
    ret = DFSUtil(a,b,visited);
    return ret;
}

int main()
{
    // Create a graph given in the above diagram
    int t,A,B,N,M,Q;
    t=scan();
    Graph g(200);
    while(t--){
    N=scan();
    M=scan();
    while(M--){
    A=scan();
    B=scan();
    if(A<N && B<N) g.addEdge(A,B);
    }
    }
    //
    Q=scan();
    while(Q--){
    A=scan();
    B=scan();
    if(A<N && B<N){
      if(g.DFS(A,B)==1)cout <<"YESn";
      else cout << "NOn";
    }
    else cout << "NOn";
    }

    return 0;
}

See Working Code at : http://ideone.com/d9hKUQ

Solution 2 : Array Based Solution

#include <iostream>
#include <list>
using namespace std;
#define gc getchar_unlocked
#define pc putchar_unlocked
inline int scan(){register int n=0,c=gc();while(c<'0'||c>'9')c=gc();while(c<='9'&&c>='0')n=(n<<1)+(n<<3)+c-'0',c=gc();return n;} 

bool findPath(int X, int Y, bool V[],int T[],int N){
if(T[X]==Y) {
//cout<<X<<Y<<"n";
return true;
}
else if(V[X]==0 && T[X]!=Y && T[X]<N ){
//cout << "temp="<<X<<"-"<<T[X]<<"n";
V[X]=1;
return findPath(V[X],Y,V,T,N);
}
else return false;
}
int findPathUtil(int X, int Y,int A[], int B[],int N){
bool VA[200]={0};
bool VB[200]={0};
bool ans = false;
//char a='a',b='b';
ans = ans || findPath(X,Y,VA,A,N) || findPath(X,Y,VB,B,N);
return ans;
}

int main()
{
    int t,N,M,Q,nn,mm,X,Y;
    t=scan();
    int A[200],B[200];
    while(t--){
    N=scan();
    M=scan();
    //int A[N],B[N];
    mm=M;
    while(M--){
    int t1=scan();
    int t2=scan();
    A[t1]=t2;
    B[t2]=t1;
    //added all entries in A,B array
    }
    }
    /*for(int i=0;i<mm;i++){
    cout << i << "=" <<A[i]<<"n";
    }*/

    Q=scan();
    while(Q--){
    X=scan();
    Y=scan();
    if(X<N && Y<N){
      if(findPathUtil(X,Y,A,B,N)==true)cout<<"YESn";
      else cout <<"NOn";
    }
    else cout << "NOn";
    }
    return 0;
}

 

See Working Code at http://ideone.com/AY4Uqr

Waiting from you to get more optimal solution