Hi. Maybe I didn't mention this but the graph is not a weighted graph so you can't sort the edges. I had an idea of scanning all the edges (u, v) and counting the all vertices v (counting all the in-degree). That could work if the graph was connected but that's not given so in order to check for connectivity to need to mark vertices so you need to initialize them. If you could check for connectivity without marking them all you could do is to check whenever vertices_discovered = |V| - 1 (not counting to root vertex). Maybe you can delete each vertex v when you scan each edge (u, v) but that doesn't seem right.
If I'll get the solution I'll make sure to share it with you guys, Alex On Sep 17, 9:04 am, "Coskun Gunduz" <[EMAIL PROTECTED]> wrote: > 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 -~----------~----~----~----~------~----~------~--~---
