|
|
first make a SCC , u will get max iterate through scc graph root nodes and in dfs the node size is great than 2 increment answer u will get min is great than 2 no, great than 1! I got AC using it What is test nubmer 4? Anybody know? maybe 6 1 1 1 1 1 1 My program can`t pass this test and i have WA4. It's like this: 15 2 5 6 3 8 2 3 6 10 10 12 13 14 15 11 The right answer is: 5 8 Edited by author 24.01.2010 23:08 No the right answer is 3 8 I keep getting WA8 but I don't have any test cases that may go wrong. Please help. I got AC for maximum temas using Kosaraju. and for minimum I started with nodes with no incoming edge and searched until it hit previously found node (cycle) this is 1 team. For disconnected cycles, run dfs in similar fashion incrementing teams by 1. This question requires knowledge of Strongly Connected Component. If you don't know read about it. Good Luck !!! for max = number of strongly connected components. for min = ? i just found no of storngly connected components and got ac in 0.562 sec after eliminating stack overflow with pragma. how to make it so fast as 0.031 sec and so little memory? You don't have to find strongly connected components. You can just sort vertices topologically and here you will find an answer :) But for topological sorting, graph must be DAG(directed acyclic)? i just keep getting stack overflow,could you please tell me how to eliminate it? min = leaves + disconnectedCycles max = acyclicNodes + disconnectedCycles + connectedCycles May be this tests can help you, my friends: 7 4 4 4 5 6 7 5 Answer: 3 5 5 4 4 4 5 5 Answer: 3 5 10 2 3 4 1 1 2 3 4 7 9 Answer: 4 7 Good luck! Edited by author 11.04.2015 21:18 Does anyone know what second test might be like? I pass all tests posted here, but can't solve this. Thanks. If you have problems with size of program stack just read FAQ and use special directives :) In pascal it is {$M 16777216} This was one of the hardest problem i implemented ( conceptually was simple ), adhoc solution, corner cases ( i had to rewrite the solution a couple of times ). Good luck with it. This was one of the hardest problem i implemented ( conceptually was simple ), adhoc solution, corner cases ( i had to rewrite the solution a couple of times ). Good luck with it. Edited by author 06.03.2012 04:35 Hi! I have tested my program for about 30 min. and still cannot find what is wrong with it. I keep getting WA 7. Can you please give a hint of what may be a reason or point some tricky part that I missed? Thanks ! Use dot from http://www.graphviz.org/ to test with random graphs, e.g., 21 1 2 1 2 1 2 5 3 4 3 4 5 6 5 4 3 5 1 2 7 20 #13 21 Can I have a sample input that would pass test 7? thanks Hello, I've WA5 can you give me some tests,please? |
|
|