Codeforces - D.Substring !

general
1

Can anyone tell me what’s the need of topological sort in this question ?? Cant we do this just running DFS on any random node and continuing until all the nodes are visited and in DFS we keep an array of size 26 in each node and store the count of that current character and update the child node array accordingly and when we are done with a path (root to leaf) we take maximum count of that array in current node(leaf node) ! And finally printing the count ! If there is a cycle print -1 instead ! My code fails for the 3rd sample case !

Ques : http://codeforces.com/problemset/problem/919/D
My code : http://codeforces.com/contest/919/submission/38124119

Pls help !1

2

instead of using union you should use a simple dfs. The problem is that you are merging two nodes which are in different branches of root and thus they will not form a cycle (back edges) but when you are merging they are joined and hence any children of the other branch seems to form a cycle(having same parent) which is actually not the case!

3

thanks bro ! got it !