You will have to add logic to your program to detect CCCs (circular sub-paths), bridge nodes (if any) and the number of CCCs a bridge node connects. After this, keep on subtracting the visits to bridge node from the number of CCCs it connects; when this becomes zero, it means that now the node can not be re-visited.
On Nov 23, 12:27 am, Sakthi Priyan <[email protected]> wrote: > I was reading about Graphs. Almost all texts, are solving problems with > acyclic graphs only. So I just wanted to try cyclic graph. > > Carlos, > > As you said, its really difficult to come up with a generic solution it > seems... But still me and my friend Shyam is working on this. We are just > discussing all the possibilities like 'using a counter in the node and > incrementing it till it reaches the degree of that node, book keeping of > visited nodes from current node...' We are still working on this... *:)* > > > > On Mon, Nov 22, 2010 at 10:57 PM, Carlos Guia <[email protected]> wrote: > > reach the other. So, if I mark node 1 as visited at first, the program will > >> start from 1 and lets say it touches 2 and then it ll touch 3. From 3, it > >> has to go to 1 and by that time node 1 is marked as visited. So program 'll > >> halt there and 'll give wrong result. > > > This part, for that example, can easily be solved as this > > > for each node n, > > mark all nodes as not visited > > start walk from n > > end for > > > However, I don't hit that solves the problem you want, I'm pretty sure > > there are other graphs that actually need to visit a node more than once. I > > haven't put much thought to it, but the problem the strikes me as NP-hard. > > If I'm correct, then you shouldn't be able to solve it efficiently for the > > general case. For a small number of nodes you could backtrack or use dynamic > > programming. > > > Where does this problem come? Is it a contest problem, you created it out > > of curiosity, school assignment, etc? > > > Carlos Guía > > > On Mon, Nov 22, 2010 at 4:37 AM, Sakthi Priyan < > > [email protected]> wrote: > > >> I am sorry. I didn't explain my problem clearly at first shot. > > >> It goes like this > > >> Assume there are five nodes in a graph. I am giving the Adjacency Matrix > >> here. > > >> 1 2 3 4 5 > >> 1 0 1 1 1 1 > >> 2 1 0 1 0 0 > >> 3 1 1 0 0 0 > >> 4 1 0 0 0 1 > >> 5 1 0 0 1 0 > > >> Now I need to visit all the nodes with minimum weights crossed. This is > >> the problem :( > > >> Here we have two closely connected components (CCC), 123 and 145. And node > >> 1 acts like a bridge between those CCC. If I enter any of those CCC, I need > >> to touch node 1 again to reach the other. So, if I mark node 1 as visited > >> at > >> first, the program will start from 1 and lets say it touches 2 and then it > >> ll touch 3. From 3, it has to go to 1 and by that time node 1 is marked as > >> visited. So program 'll halt there and 'll give wrong result. > > >> Please suggest... > > >> On Mon, Nov 22, 2010 at 9:52 AM, vineel yalamarth < > >> [email protected]> wrote: > > >>> Try using a visited flag for all the nodes. Initialise it to zero and > >>> toggle it when you traverse through it,.Based on status of visited flag, > >>> you > >>> can avoid visiting the visited nodes. > > >>> Regards, > >>> Vineel. > > >>> -- > >>> You received this message because you are subscribed to the Google Groups > >>> "google-codejam" group. > >>> To post to this group, send email to [email protected]. > >>> To unsubscribe from this group, send email to > >>> [email protected]<google-code%[email protected]> > >>> . > >>> For more options, visit this group at > >>>http://groups.google.com/group/google-code?hl=en. > > >> -- > >> - Thanks and Regards, > > >> *Sakthipriyan* > > >> -- > >> You received this message because you are subscribed to the Google Groups > >> "google-codejam" group. > >> To post to this group, send email to [email protected]. > >> To unsubscribe from this group, send email to > >> [email protected]<google-code%[email protected]> > >> . > >> For more options, visit this group at > >>http://groups.google.com/group/google-code?hl=en. > > > -- > > You received this message because you are subscribed to the Google Groups > > "google-codejam" group. > > To post to this group, send email to [email protected]. > > To unsubscribe from this group, send email to > > [email protected]<google-code%[email protected]> > > . > > For more options, visit this group at > >http://groups.google.com/group/google-code?hl=en. > > -- > - Thanks and Regards, > > *Sakthipriyan* -- You received this message because you are subscribed to the Google Groups "google-codejam" 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/google-code?hl=en.
