We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I'm getting off by one for half the test cases and cant seem to see why. Can anyone help? I performed BFS from a node u, returning node v, where node v is at maximal distance from u. Then i marked all nodes in the predecessor path from v back to u as black. Then I ran a DFS on all remaining nodes to find the diameter of all trees in the forest created by not considering black nodes, taking the maximal of all these diameters and adding it to the diameter of the original graph (the length of the predecessor path from v back to u). This should work!
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Maximal Tree Diameter
You are viewing a single comment's thread. Return to all comments →
I'm getting off by one for half the test cases and cant seem to see why. Can anyone help? I performed BFS from a node u, returning node v, where node v is at maximal distance from u. Then i marked all nodes in the predecessor path from v back to u as black. Then I ran a DFS on all remaining nodes to find the diameter of all trees in the forest created by not considering black nodes, taking the maximal of all these diameters and adding it to the diameter of the original graph (the length of the predecessor path from v back to u). This should work!