Re: [algogeeks] Re: A graph problem
find the size of smallest cycle in the given graph ... tarjan should do the trick.. dfs basically ... :) On Thu, Jan 5, 2012 at 7:02 PM, WgpShashank shashank7andr...@gmail.comwrote: @Saurabh DFS Should Work Here, Start from any room i , visit next room connected to it .. then to this room so on , once you back track you will back to the starting node ,this way you can find out .min.umber of room he need to visit will be 2 times of traversal isn't it ? posting the soln in hurry :), i know may have some bugs , will discuss after some time. Thanks Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/El6uttSxuA0J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: A graph problem
Yes I also initially thought soBut how do we take into consideration the edge weights??The cycle can include such edges whose total cost may come negative. Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Thu, Jan 5, 2012 at 10:01 PM, karthikeyan muthu keyankarthi1...@gmail.com wrote: find the size of smallest cycle in the given graph ... tarjan should do the trick.. dfs basically ... :) On Thu, Jan 5, 2012 at 7:02 PM, WgpShashank shashank7andr...@gmail.comwrote: @Saurabh DFS Should Work Here, Start from any room i , visit next room connected to it .. then to this room so on , once you back track you will back to the starting node ,this way you can find out .min.umber of room he need to visit will be 2 times of traversal isn't it ? posting the soln in hurry :), i know may have some bugs , will discuss after some time. Thanks Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/El6uttSxuA0J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: A Graph Problem
Maybe this problem is related to pigeon hole problem On Mon, May 30, 2011 at 8:44 AM, Aakash Johari aakashj@gmail.comwrote: No, won't work. :( On Sun, May 29, 2011 at 11:39 PM, Aakash Johari aakashj@gmail.comwrote: Can this solution work? Create adjacency matrix where adj[i][j] representing person i doesnt like person j. Now toggle the relations (means now the adj[i][j] will represent person i and person j can live with each other) and find the no. of connected components. No. of connected components will be the number of rooms required. On Sun, May 29, 2011 at 11:29 PM, Aakash Johari aakashj@gmail.comwrote: yes, sorry.. i misunderstood the problem. On Sun, May 29, 2011 at 11:24 PM, anshu mishra anshumishra6...@gmail.com wrote: biaprtie graph is special case when we can color the whole graph just by two colors. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Aakash Johari (IIIT Allahabad) -- -Aakash Johari (IIIT Allahabad) -- -Aakash Johari (IIIT Allahabad) -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: A Graph Problem
Bipartite Graph.. On Sun, May 29, 2011 at 9:42 PM, ross jagadish1...@gmail.com wrote: @anshu mishra: Yeah. Thanks! :) On May 30, 8:26 am, anshu mishra anshumishra6...@gmail.com wrote: it is exactly a graph coloring problem. so it has no polynomial order solution. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Aakash Johari (IIIT Allahabad) -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: A Graph Problem
biaprtie graph is special case when we can color the whole graph just by two colors. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: A Graph Problem
yes, sorry.. i misunderstood the problem. On Sun, May 29, 2011 at 11:24 PM, anshu mishra anshumishra6...@gmail.comwrote: biaprtie graph is special case when we can color the whole graph just by two colors. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Aakash Johari (IIIT Allahabad) -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: A Graph Problem
Can this solution work? Create adjacency matrix where adj[i][j] representing person i doesnt like person j. Now toggle the relations (means now the adj[i][j] will represent person i and person j can live with each other) and find the no. of connected components. No. of connected components will be the number of rooms required. On Sun, May 29, 2011 at 11:29 PM, Aakash Johari aakashj@gmail.comwrote: yes, sorry.. i misunderstood the problem. On Sun, May 29, 2011 at 11:24 PM, anshu mishra anshumishra6...@gmail.comwrote: biaprtie graph is special case when we can color the whole graph just by two colors. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Aakash Johari (IIIT Allahabad) -- -Aakash Johari (IIIT Allahabad) -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: A Graph Problem
No, won't work. :( On Sun, May 29, 2011 at 11:39 PM, Aakash Johari aakashj@gmail.comwrote: Can this solution work? Create adjacency matrix where adj[i][j] representing person i doesnt like person j. Now toggle the relations (means now the adj[i][j] will represent person i and person j can live with each other) and find the no. of connected components. No. of connected components will be the number of rooms required. On Sun, May 29, 2011 at 11:29 PM, Aakash Johari aakashj@gmail.comwrote: yes, sorry.. i misunderstood the problem. On Sun, May 29, 2011 at 11:24 PM, anshu mishra anshumishra6...@gmail.com wrote: biaprtie graph is special case when we can color the whole graph just by two colors. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Aakash Johari (IIIT Allahabad) -- -Aakash Johari (IIIT Allahabad) -- -Aakash Johari (IIIT Allahabad) -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
