After listening to the news of testing of Delivery Drones by ....
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 <<"YES\n";
else cout << "NO\n";
}
else cout << "NO\n";
}
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<<"YES\n";
else cout <<"NO\n";
}
else cout << "NO\n";
}
return 0;
}
See Working Code at http://ideone.com/AY4Uqr
Waiting from you to get more optimal solution
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 <<"YES\n";
else cout << "NO\n";
}
else cout << "NO\n";
}
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<<"YES\n";
else cout <<"NO\n";
}
else cout << "NO\n";
}
return 0;
}
See Working Code at http://ideone.com/AY4Uqr
Waiting from you to get more optimal solution
