Daisy Chains in the Field

The usage problem of Daisy chains in the field is extremely hard!
Can anyone solve this??!!
Daisy Chains in the Field

Farmer John let his N (1 <= N <= 250) cows conveniently numbered
1..N play in the field. The cows decided to connect with each other
using cow-ropes, creating M (1 <= M <= N*(N-1)/2) pairwise connections.
Of course, no two cows had more than one rope directly connecting
them. The input shows pairs of cows c1 and c2 that are connected
(1 <= c1 <= N; 1 <= c2 <= N; c1 != c2).

FJ instructed the cows to be part of a chain which contained cow
#1. Help FJ find any misbehaving cows by determining, in ascending
order, the numbers of the cows not connected by one or more ropes
to cow 1 (cow 1 is always connected to herself, of course). If there
are no misbehaving cows, output 0.

To show how this works, consider six cows with four connections:

1---2 4---5
\ |
\ | 6

Visually, we can see that cows 4, 5, and 6 are not connected to cow 1.



* Line 1: Two space-separated integers: N and M

* Lines 2..M+1: Line i+1 shows two cows connected by rope i with two
space-separated integers: c1 and c2


6 4
1 3
2 3
1 2
4 5


* Lines 1..???: Each line contains a single integer


Last edited on
1. Paint cow 1 green.
2. Let S1 be the set of cows currently painted green and S2 the set of unpainted cows connected to any cow in the S1 set.
3. If S1 is empty, go to step 7.
4. Paint red every cow in S1.
5. Paint green every cow in S2.
6. Go to step 2.
7. All cows are now either painted red or unpainted. All unpainted cows are considered misbehaving.
Last edited on
Topic archived. No new replies allowed.