Clarifying the task --- Breadth First Search --- Task 154
Back to Problem Solutions forum
Hello, everyone! I am in difficulty to understand the task at all. Could you please to clarify next:
- Input data - is it all about one Graph?
- Assume that 1 question has answer yes. Then, initial node 7 with 10 edges, right?
- Then how it is possible that there are two pais (6 3) and (6 5)? Node 6 has different amount of edges within same Graph?
- Assume that 1 question has answer no. Then (7 10) - first graph, (0 1) - second etc. ... looks like 11 graphs, but answer is only for (7 10), isn't it?
Please help with this simple questions. I've read Lafore's Graphs chapter and tested the codes, I would say I caught the idea about Graphs... But I cannot understand the task and how to apply the theory. Thanks in advance!
Hi Sergey,
1 and 2, Yes and Yes
3 The graph in the input data is the same as the graph shown at the top of the page, but with A=0, B=1, ... G=6
Hi, Quandray! Thanks for reply, but then I can't understand how it is possible that there are two pais (6 3) and (6 5)? Node 6 has different amount of edges within same Graph?
Node 6, or node G in the picture, has 3 edges. Those are (6 3) G to D, (6 5) G to F and (4 6) E to G.
On that graph some nodes have 2 undirected edges, some 3 undirected edges and node D has 4 undirected edges.
By "undirected" I mean that they can be used to enter or leave a node.
Does that help? If not please ask again.
It does help! No question for now. I'll try again to solve the task, now with more understanding. Thanks!
Hello! New questions. I've created a programm that works fine with the example input (7 10 0 1 2 0 0 3 1 4 4 3 2 3 5 2 6 3 4 6 6 5 )
And as shown in task I got the same answer: -1 0 0 0 1 2 3 So questions:
Am right in:
From 0 we visit 1
From 0 we visit 2
From 0 we visit 3
From 1 we visit 4
From 2 we visit 5
From 3 we visit 6
?
Why the answer for real task data can be started form some numbers but not from "0"? I mean "0" is the first and main vertex, then all answers must be started form 0 0 0 0 etc. Or I misunderstood something?
Yes, sure. And if start from zero, how it's possible that the real answer starts from some number but not "0" If we start with zero, then first numbers in answer must be zero, because we have to show elements from wich we visit the next vertices. Here is real test data: 43 112 3 38 35 42 14 37 11 4 22 12 32 33 36 7 36 17 3 4 26 21 11 33 12 34 9 27 2 9 29 13 24 36 19 20 11 41 40 4 23 33 27 39 31 28 0 29 42 11 17 16 42 37 29 25 25 18 26 1 38 20 27 13 35 28 25 15 8 24 37 17 14 15 37 18 23 2 33 9 25 5 13 8 1 22 37 10 22 4 1 36 20 22 1 12 34 30 38 39 41 9 14 31 31 21 31 0 23 26 40 7 4 21 0 41 13 5 13 19 24 35 20 1 6 39 15 23 19 15 17 9 4 17 26 41 40 1 6 12 27 15 6 10 8 28 29 16 16 37 4 39 4 26 30 17 5 35 5 38 0 1 36 34 32 15 26 12 37 22 35 14 2 35 42 7 28 12 7 27 10 25 30 32 40 13 42 20 18 36 25 11 39 10 20 40 34 24 36 30 26 25 32 39 33 10 23 5 19 16 34 31 26 33 37 31 39 29 14 34 20 12 41 10 29 2
My answer is
-1 0 0 0 1 1 1 1 1 1 29 29 29 29 29 31 31 31 31 31 41 41 41 12 20 20 20 22 26 26 36 36 36 36 36 2 13 13 13 25 39 38
Correct answer is
-1 0 29 38 22 13 12 36 13 41 41 41 1 29 31 25 29 36 36 20 1 31 1 26 36 29 1 13 31 0 36 0 39 26 31 2 1 31 20 29 1 0 20
Why (29 38 etc.)? Why in correct answer 0 somewhere in the end? If we start with 0, then at first all vertices from 0, then first several numbers in answer must be 0. Please help...
In that test data, there are the pairs (0,29) (31,0) (0,41) & (0,1)
In the expected output, positions 1, 29, 31 & 41 are zero, which means that those nodes were reached from node zero.
Can't find where is zero? From the start of pair list 0-29 is 23d. But in answer zero is on second, 29th etc. Also zero last but one but in the task there is pair 41-10. Still don't understand, sorry...
The order of the pairs in the input is not important. The 0-29 pair could be anywhere in the input. The 0-29 pair only means that there is an edge between nodes 0 and 29.
When you start the BFS from node 0, the adjacent nodes (seen from node 0) are 1, 29, 31 & 41.
There are 43 nodes numbered 0 to 42. In the output there are 43 positions numbered 0 to 42. Positions 1, 29, 31 & 41 of the output contain zero, showing that those nodes (1, 29, 31 & 41) were seen from node 0.
If you still don't understand, please keep asking.
I understand the idea that 1, 29, 31 & 41 were seen from 0, I don't understand why the answer is not started from those four zeroes.
(-1) - OK, this is zero - first node and it can't be seen from any another nodes. So let's imagine the process. We take out the zero from a queue and visit 1 than 29 than31, than 41. So answer must be started like: -1 0 0 0 0 (those four times of zero from which we visit 1, 29,...) Then we remove 1 and according to the input data above we see pairs: (1 12) (20 1) (1 22) (26 1) (1 36) (40 1) They tell us that we can visit 12 20 22 26 36 40 from vertex 1 then +5 times of 1 in the answer must be added. -1 0 0 0 1 1 1 1 1 1.... In the Correct answer I've also counted 5 of 1, but I can't undersand the order of Correct answer. Why they are all scattered?
The expected answer starts with -1 0 29 38 22 13 12
-1 means that node 0 is the start node
0 means that node 1 was seen from node 0
29 means that node 2 was seen from 29
38 means that node 3 was seen from 38
22 means that node 4 was seen from 22
13 means that node 5 was seen from 13