USACO 2015 January Contest, Gold
Problem 3. Grass Cownoisseur
Contest has ended.
Log in to allow submissions in analysis mode
Problem 3: Grass Cownoisseur [Mark Gordon, 2015]
In an effort to better manage the grazing patterns of his cows, Farmer
John has installed one-way cow paths all over his farm. The farm
consists of N fields, conveniently numbered 1..N, with each one-way
cow path connecting a pair of fields. For example, if a path connects
from field X to field Y, then cows are allowed to travel from X to Y
but not from Y to X.
Bessie the cow, as we all know, enjoys eating grass from as many
fields as possible. She always starts in field 1 at the beginning of
the day and visits a sequence of fields, returning to field 1 at the
end of the day. She tries to maximize the number of distinct fields
along her route, since she gets to eat the grass in each one (if she
visits a field multiple times, she only eats the grass there once).
As one might imagine, Bessie is not particularly happy about the
one-way restriction on FJ's paths, since this will likely reduce the
number of distinct fields she can possibly visit along her daily
route. She wonders how much grass she will be able to eat if she
breaks the rules and follows up to one path in the wrong direction.
Please compute the maximum number of distinct fields she can visit
along a route starting and ending at field 1, where she can follow up
to one path along the route in the wrong direction. Bessie can only
travel backwards at most once in her journey. In particular, she
cannot even take the same path backwards twice.
INPUT: (file grass.in)
The first line of input contains N and M, giving the number of fields
and the number of one-way paths (1 <= N, M <= 100,000).
The following M lines each describe a one-way cow path. Each line
contains two distinct field numbers X and Y, corresponding to a cow
path from X to Y. The same cow path will never appear more than once.
SAMPLE INPUT:
7 10
1 2
3 1
2 5
2 4
3 7
3 5
3 6
6 5
7 2
4 7
OUTPUT: (file grass.out)
A single line indicating the maximum number of distinct fields Bessie
can visit along a route starting and ending at field 1, given that she can
follow at most one path along this route in the wrong direction.
SAMPLE OUTPUT: (file grass.out)
6
SOLUTION NOTES:
Here is an ASCII drawing of the sample input:
v---3-->6
7 |\ |
^\ v \ |
| \ 1 \|
| \| v
| v 5
4<--2---^
Bessie can visit pastures 1, 2, 4, 7, 2, 5, 3, 1 by traveling
backwards on the path between 5 and 3. When she arrives at 3 she
cannot reach 6 without following another backwards path.
Contest has ended. No further submissions allowed.