Hi, If I'm not wrong, you don't have to find a root node. You only need to check if a given node u is root or not.
Actually O(E) seems too low to me for this. I think this problem can be solved in O(E) if it's been reduced to some other problems. I tried using prime factors, but couldn't make it work. I represented each node with a prime and edges with the multiplication of these primes, but it needs so much calculation. Maybe you should try XOR'ing on the adjacency matrix, but I'm not sure if it works. O(ElogE) may be possible, by first sorting the edges, then binary search among them. Well, it's an interesting problem, we'd be glad if you share the solution when you get it. best, coskun... On Tue, Sep 16, 2008 at 8:42 PM, Alex Snast <[EMAIL PROTECTED]> wrote: > > hello. > > I've been cracking my head on a question from a test and i'm still not > sure how to solve this. > > Quesion: > > Given G = (V, E) , a directed graph. a vetex u is called a root iff > there's a path from it to all the other vertices in G > > Suggest an algorithm that checks whenever vertex u is a root: > > runtime: O(E) , so i simple BFS o DFS won't work. > > Thanks for your help guys. > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
