DONT GET WET
All submissions for this problem are available.
In VSSUT, different departments are connected to each other except CSE-IT department, Workshop and Hydrolics lab. For this problem assume that VSSUT has N departments and some of them are connected to each other. Suppose you are in one of the departments and are trying to reach another one. But it suddenly started to rain. If your destination department happens to be connected (directly or indirectly) to the department you are currently in, you can go there without getting wet. Otherwise you will get wet. (See explanation of test case for clarification).
For simplicity, let us assume that the departments are numbered from 1 to N. You are given which departments are connected, your present location and your destination. Your task is simple. Find whether or not you can reach your destination without getting wet..
The first line gives an integer T denoting the number of test cases. Each test
case starts with two numbers N and C denoting the number of departments and number of
connected parts. Next C lines contain two integers a and b each denoting which departments are
connected. Next line contains one number Q denoting number of queries. Each query contains two
numbers s and d denoting your present location and your destination.
For each query print “Yes” if it is possible to reach destination without getting
wet. Otherwise print “No”. (Quotes are for clarifications only)..
- 1 <= T <= 10
- 1 < N <= 10^6
- 1 < Q <= 10^6
- 1 <= a,b,s,d <= N
- 1 < N <= 10^6
Input: 1 7 5 1 2 1 5 1 4 2 4 6 7 5 1 4 2 3 6 7 7 4 5 4 Output: Yes No Yes No Yes
First four queries are self-explainable. For fifth one, department 5 is connected to department 1 which is in turn connected to department 4. So you can travel from department 5 to 1 and then from 1 to 4.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA|
Fetching successful submissions
If you are still having problems, see a sample solution here.