Daisy Chains in the Field
InterviewTime limit1sMemory limit128 MB
Given an undirected graph of cows joined by ropes, list in ascending order every cow that cannot reach cow 1, or print 0 if all cows are connected to it.
- Level
Easy3 of 10
- Topics
- Graph, DFS, BFS, Implementation
- Solved
- No attempts yet
Problem
Farmer John lets his () cows, numbered , play in the field. The cows tie themselves to one another with cow-ropes, forming () pairwise connections. No two cows are joined by more than one rope. Each connection is given as a pair of cows and (; ; ).
Farmer John wants every cow to belong to the same chain as cow . Help him spot the misbehaving cows: report, in ascending order, the numbers of the cows that are not linked to cow through one or more ropes (cow is, of course, always linked to herself). If there are no misbehaving cows, output .
To illustrate, consider six cows with four connections:
1---2 4---5
\ |
\ | 6
\|
3
Here cows , , and are not linked to cow .
Input
- Line : two space-separated integers, and .
- Lines : line describes rope with two space-separated integers and , the two cows it connects.
Output
- Output one integer per line: the numbers of the cows not linked to cow , in ascending order.
- If every cow is linked to cow , output a single line containing .