|
|
6 11 1 1
1 2
1 3
3 1
3 2
2 6
2 4
3 5
5 5
5 4
4 6
6 4
Answer: 0 If there is cycle in graph then -1,
if path from S to T does not exist then -1,
else 1. My Ac prog gives 2
on
10 11 1 10
1 5
5 10
5 1
1 2
2 3
3 4
4 2
4 7
7 8
8 7
8 10
By the way.
Answer may be ~ 50000
Also: To find all circles is very difficult.
To find strong components: this is helped me to break long sequence of TLE Can you give an idea of solution with StrConnected Comp? You must take in account that only 26 TopCoders has solved
this probem. It rather involved and demand
education level.
For your training only I can said:
1. If stronng comp is not simple circle and
can be go in from s and after t is achivebale then: -1
2. If only simple circles we met then: it's number mines one.
it is coin change asymptotics. I'd say if the path from S to T does not exist then we should output 0. if from t to s is possible then result=1
else result=-1
use Adjacency List to express the graph |
|
|
