### determinism's blog

By determinism, history, 5 years ago, , I was trying solve this problem and I've thought of O(T * N) solution that uses Tarjan+DP. I thought O(T * N 2) wouldn't work because . But solutions on this blog and this blog seem to me as O(T * N 2).

How do they get accepted? Is it just because of weak test cases, or is there something else I'm missing here?  Comments (7)
 » 5 years ago, # | ← Rev. 2 →   Their dfs does not visit a vertex twice, that's why it's O(N) not O(N 2) nvm
•  » » It can visit a vertex twice. These codes don't directly use previously memorized values because it's not necessarily a DAG. It just doesn't call dfs for ith node if it's traversed in the loop in main function. For example, if we have a graph like this, every vertex is visited more than once.
•  » » » Yeah, you are right. Apparently test data is weak.
•  » » » » 5 years ago, # ^ | ← Rev. 4 →   Is there any other O(T * N) solution other than Tarjan+DP?
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   I think this is mostly the same as your solution, but here is mine:Notice that the graph consists of directed cycles along with trees (directed up towards the root) where the root is contained in one of the directed cycles. These cycles and trees can be found via DFS. Each vertex in a cycle of length k will forward emails to k-1 vertices. Each vertex in a tree (except the root) whose parent forwards emails to k vertices will forward emails to k+1 vertices. These values can be propagated down the trees with any tree traversal. Then a linear search for the vertex that forwards the maximum number of emails will give us the answer.
•  » » » » » » can you please explain more the part of parent forward to k vertices and root forward to k+1 vertices does you count the "clan chieftain" as a parent ?and the first node in the cyclic or what we assume that it`s as a root ? and if that is right how could root it forward to k+1 which (k+1) could you apply your saying on the first example in the problem please thanks in advance
 » We can do that in O(N) time by finding SCC's(strongly connected components). here is the code