Grass Cownoisseur
플래티넘 I의견: 0
Farmer John has installed one-way cow paths all over his farm. The farm consists of N fields, numbered 1..N, with each one-way cow path connecting a pair of fields (a path from X to Y allows travel from X to Y but not Y to X).
Bessie always starts in field 1, visits a sequence of fields, and returns to field 1 at the end of the day. She tries to maximize the number of distinct fields along her route (visiting a field multiple times only counts once).
She wonders how much grass she could 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 in the wrong direction. She cannot take the same path backwards twice.
Line 1: N and M, the number of fields and one-way paths (1 <= N, M <= 100,000).
The following M lines each contain two distinct field numbers X and Y, a cow path from X to Y. The same cow path will never appear more than once.
A single line giving the maximum number of distinct fields Bessie can visit along a route starting and ending at field 1, following at most one path in the wrong direction.
grass.ingrass.out7 10
1 2
3 1
2 5
2 4
3 7
3 5
3 6
6 5
7 2
4 76Output details: Bessie can visit 1, 2, 4, 7, 2, 5, 3, 1 by traveling backwards on the path between 5 and 3.
평가 및 의견
Grass Cownoisseur
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Grass Cownoisseur