I was thinking of sorting alphabetically. For example edge AD comes before edge AE and BA, and so on. That may help to do a binary search over the edges, instead of linear search.
I'll try to improve your idea if I can, best, coskun... On Wed, Sep 17, 2008 at 11:00 AM, Alex Snast <[EMAIL PROTECTED]> wrote: > > 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 [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
