[algogeeks] Re: A graph problem
@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.
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.
[algogeeks] Re: A graph problem
The problem with the proposed depth first search is that it can try many very long paths, requiring exponential time, before it ever finds the correct cycle, even if the cycle is very short. A breadth-first search will avoid this, and using dynamic programming principles can accomplish the equivalent of a breadth-first search without excessively large memory requirements. Use an nxn table H[n][n] to represent the possible states after t moves. H[i][j] is the possible happiness at time t for a person starting at room i and now in room j. Start with the table initialized to min, a very large negative value, and the diagonal set to zero. This indicates that at t=0, you could start in any room with zero happiness. Then increment t and compute the new H, where H[i][j] is the maximum value of H[i][k]+Ckj for all values of k. As soon as you have a positive value in the diagonal, t is the length of the shortest cycle. Don On Jan 5, 7:07 am, saurabh singh saurab...@gmail.com wrote: This problem is taken fromwww.codeforces.com.Whatcan be the possible approaches?? A smile house is created to raise the mood. It has *n* rooms. Some of the rooms are connected by doors. For each two rooms (number *i*and *j*), which are connected by a door, Petya knows their value *c**ij* — the value which is being added to his mood when he moves from room *i* to room *j*. Petya wondered whether he can raise his mood infinitely, moving along some cycle? And if he can, then what minimum number of rooms he will need to visit during one period of a cycle? Input The first line contains two positive integers *n* and *m* (), where *n* is the number of rooms, and *m* is the number of doors in the Smile House. Then follows the description of the doors: *m* lines each containing four integers *i*, *j*, *c**ij* и *c**ji* (1 ≤ *i*, *j* ≤ *n*, *i* ≠ *j*, - 104≤ *c**ij*, *c**ji* ≤ 104). It is guaranteed that no more than one door connects any two rooms. No door connects the room with itself. Output Print the minimum number of rooms that one needs to visit during one traverse of the cycle that can raise mood infinitely. If such cycle does not exist, print number 0. Sample test(s) input 4 4 1 2 -10 3 1 3 1 -10 2 4 -10 -1 3 4 0 -3 output 4 Note Cycle is such a sequence of rooms *a*1, *a*2, ..., *a**k*, that *a*1 is connected with *a*2, *a*2 is connected with *a*3, ..., *a**k* - 1 is connected with *a**k*,*a**k* is connected with *a*1. Some elements of the sequence can coincide, that is, the cycle should not necessarily be simple. The number of rooms in the cycle is considered as *k*, the sequence's length. Note that the minimum possible length equals two. Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com -- 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.
[algogeeks] Re: A Graph Problem
@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.
[algogeeks] Re: another graph problem
@Jeth Hi Just thot a Soln Since we need to check whether the length of any path btw any two nodes in a grph it s enough if we checkwhether the Height of DFS tree [/Forest] is max of 2. If so then the ttask underlying is accomplished. Notify if my intution s not crt Open 4 comments Regards Bala On May 5, 8:42 pm, jeth [EMAIL PROTECTED] wrote: Hi, for a long time I'm having a problem with one graph algorithm. After checking two and spending few days on it I've no more ideas what to do. Maybe you can give me some pieces of advice which algorithm should I use to solve such problem: Assume we have a n-vertice graph with m-edges. The edges are given in input. My task is to find if it is possible to connect each vertice with exactly two other vertices. Every edge can be used two times. The maximum lenght of path which connects two vertices is 3. For graph with edges 1 2 2 3 the answer is YES, because we can make such connections: 1-2 2-3 1-2-3 I'll be greatful for any possible help. regards, Jeth --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: A graph problem
there are existing algorithms to find connected components which wud do it. On 3/30/07, Mofid [EMAIL PROTECTED] wrote: Hello! We have a graph that is not directional. We want an algorithm to find out if this graph is divided to two parts or not. mofid --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: A graph problem
- Original Message - From: Mofid [EMAIL PROTECTED] To: Algorithm Geeks algogeeks@googlegroups.com Sent: Saturday, March 31, 2007 12:28 AM Subject: [algogeeks] A graph problem Hello! We have a graph that is not directional. We want an algorithm to find out if this graph is divided to two parts or not. mofid Two words -- flood fill Muntasir --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: A graph problem
DFS --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
