The usage problem of Daisy chains in the field is extremely hard!

Can anyone solve this??!!

Problem:

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

\|

3

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

PROBLEM NAME: daisy

INPUT FORMAT:

* 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

SAMPLE INPUT:

6 4

1 3

2 3

1 2

4 5

OUTPUT FORMAT:

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

SAMPLE OUTPUT:

4

5

6

Can anyone solve this??!!

Problem:

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

\|

3

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

PROBLEM NAME: daisy

INPUT FORMAT:

* 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

SAMPLE INPUT:

6 4

1 3

2 3

1 2

4 5

OUTPUT FORMAT:

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

SAMPLE OUTPUT:

4

5

6

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.

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.