I don't think binary search will help you here. Think about it, worst case you can have a path graph so you'll have to do a linear search. Oh wait I think i got it! How about the following: If |E| < |V| - 1 the answer is obviously false. So |E| is about |V| (sparse graph) or |E| is about |V|^2 (dense graphs). Now if you ran say a BFS that has a runtime of O(|V|+|E|) but since E is |V| or more we get O(E).
On Sep 17, 11:58 am, "Coskun Gunduz" <[EMAIL PROTECTED]> wrote: > 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 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 -~----------~----~----~----~------~----~------~--~---
