10959 - The Party, Part I
Solution Description : Graph (BFS) Problem For Input: 5 5 0 1 1 2 2 3 3 4 0 4 0 step: you got person 0 (Giovanni) 1 step: you got persons 1 and 4. because 1 and 4 are dancing partner of 0 step person 0. 2 step: you got persons 2 and 3. because 2 is dancing partner of 1 (1 step) and 3 is dancing partner of 4. Now you got all person so ans is: person - step 1 - 1 2 - 2 3 - 2 4 - 1 This is a simple BFS problem Run BFS from person 0 with step 0. Find adjacency of 0 and push to queue with step of person 0 + 1 continue the process until the queue is not empty. Now print the step number where you got this person. |
||||||||||