TDBFS  Searching the Graph
Wersja polska  English version 
For a given list of adjacent vertices of a graph and a chosen vertex v write down in the Depth First Search (DFS) or Breadth First Search (BFS) order all the vertices from the connected component of the graph containing v. Assume that the number of vertices of the graph is at most 1000.
Input
t [the number of graphs <= 100]
Graph:
n [1 <= n <= 1000 the number of graph vertices]
i m a b c ... [the list of m adjacent vertices to vertex i]
Any query is as follows: [not more than n queries]
v i
where 1 <= v <= n is the beginning vertex and i = 0 for DFS order and i = 1 for BFS order.
0 0 [at the end of the serie]
The list for isolated vertex a is a 0.
Output
graph i [test case, word graph is necessary]
a b c ... [the DFS or BFS order of all vertices]
Example
Input: 3 6 1 2 3 4 2 2 3 6 3 2 1 2 4 1 1 5 0 6 1 2 5 1 1 0 1 0 0 0 10 1 6 3 5 6 7 8 9 2 1 9 3 2 1 5 4 5 6 7 8 9 10 5 4 1 3 7 8 6 3 1 4 7 7 5 1 4 5 6 8 8 5 1 4 5 7 10 9 3 1 2 4 10 2 4 8 7 1 1 0 2 1 4 1 7 1 0 0 2 1 0 2 0 1 1 0 0 Output: graph 1 5 1 3 2 6 4 1 3 2 6 4 graph 2 7 1 4 5 6 8 3 9 10 2 1 3 5 7 4 6 8 10 9 2 2 9 1 4 3 5 6 7 8 10 4 6 7 8 9 10 1 5 2 3 7 1 4 5 6 8 3 9 10 2 graph 3 1
hide comments
martinho_11235:
20181018 01:39:54
Good problem for those that are starting to solve BFS and DFS problem... Last edit: 20181018 01:40:36 

kamran siddique:
20160408 21:44:34
1st Go :) 

Amir Najjar:
20160308 17:26:30
AC on first submit


sabri:
20160302 20:26:38
may someone explain this prolbleù statment??


bourne:
20160227 09:53:53
would any DFS solution not work? Do we necessarily need to order them according to input? 

Nehal J Wani:
20151207 11:16:07
"[not more than n queries]" is a lie. 

hashem sllat:
20151016 17:18:19
cake of piece :D 

ericleoo:
20150703 20:41:01
This problem is not clear at all 

Kishlay Raj:
20141031 00:38:37
in dfs its pushing the nodes in reverse order i.e. the one with higher value get pushed first 

LeppyR64:
20141031 00:38:37
Use a preorder traversal. Order the edges on the order they are input. Last edit: 20111125 16:22:25 
Added by:  mima 
Date:  20041022 
Time limit:  15s 
Source limit:  5000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 