fork download
copy 
  1. #include <iostream>
  2. #include <list>
  3.  
  4. using namespace std;
  5.  
  6. #define gc getchar_unlocked
  7. #define pc putchar_unlocked
  8. 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;} 
  9.  
  10. class Graph
  11. {
  12.     int V;    // No. of vertices
  13.     list<int> *adj;    // Pointer to an array containing adjacency lists
  14.     int DFSUtil(int a ,int b, bool visited[]);  // A function used by DFS
  15. public:
  16.     Graph(int V);   // Constructor
  17.     void addEdge(int a ,int b);   // function to add an edge to graph
  18.     int DFS(int a ,int b);    // DFS traversal of the vertices reachable from v
  19. };
  20.  
  21. Graph::Graph(int V)
  22. {
  23.     this->V = V;
  24.     adj = new list<int>[V];
  25. }
  26.  
  27. void Graph::addEdge(int v, int w)
  28. {
  29.     adj[v].push_back(w);
  30.     adj[w].push_back(v);
  31. }
  32.  
  33. int Graph::DFSUtil(int a, int b, bool visited[])
  34. {
  35.     // Mark the current node as visited and print it
  36.     int ret=0;
  37.     visited[a] = true;
  38.     //out <<"Nodes= " << a <<"\n";
  39.  	if(a == b) return 1;
  40.     // Recur for all the vertices adjacent to this vertex
  41.     list<int>::iterator i;
  42.     for(i = adj[a].begin(); i != adj[a].end(); ++i)
  43.         if(!visited[*i]){
  44.             ret = DFSUtil(*i,b, visited);
  45.             return ret;
  46.             }
  47.  
  48. }
  49. int Graph::DFS(int a, int b)
  50. {
  51.     // Mark all the vertices as not visited
  52.     bool *visited = new bool[V];
  53.     int ret=0;
  54.     for(int i = 0; i < V; i++)
  55.         visited[i] = false;
  56.     ret = DFSUtil(a,b,visited);
  57.     return ret;
  58. }
  59.  
  60. int main()
  61. {
  62.     // Create a graph given in the above diagram
  63.     int t,A,B,N,M,Q;
  64.     t=scan();
  65.     Graph g(200);
  66.     while(t--){
  67.     	N=scan();
  68.     	M=scan();
  69.     	while(M--){
  70.     		A=scan();
  71.     		B=scan();
  72.     		if(A<N && B<N) g.addEdge(A,B);
  73.     	}
  74.     }
  75.     //
  76.     Q=scan();
  77.     while(Q--){
  78.     A=scan();
  79.     B=scan();
  80.     if(A<N && B<N){
  81.       if(g.DFS(A,B)==1)cout <<"YES\n";
  82.       else cout << "NO\n";
  83.     }
  84.     else cout << "NO\n";
  85.     }
  86.  
  87.  
  88.     return 0;
  89. }
Success #stdin #stdout 0s 3480KB
comments ()
stdin
copy 
1
4 2
0 1
1 2
3
0 2
0 3
2 1
stdout
copy 
YES
NO
YES
https://ideone.com/d9hKUQ
Flipkart's Drones HE Graph Solution
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!