|
|
| Show all threads Hide all threads Show all messages Hide all messages | | WA22 | andreyDagger`~ | 1691. Algorithm Complexity | 7 Aug 2023 00:30 | 1 | WA22 andreyDagger`~ 7 Aug 2023 00:30 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 | | Is my idea right? | Lebedev_Nicolay[Ivanovo SPU] | 1691. Algorithm Complexity | 13 Mar 2010 02:20 | 5 | 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. | | how about the idea? | program_lover | 1691. Algorithm Complexity | 14 Mar 2009 15:35 | 1 | if from t to s is possible then result=1
else result=-1
use Adjacency List to express the graph |
|
|
|
