[algogeeks] A graph problem
This problem is taken from www.codeforces.com.What can 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] A Graph Problem
Consider each person as a node on a graph. Two nodes are connected only when both persons like each other. Now do any traversal of this graph to find the number of connected components. That should be the minimum no. of houses required. On Sun, May 29, 2011 at 9:17 PM, ross wrote: > There are n persons. > You are provided with a list of ppl which each person does not like. > Determine the minm no. of houses required such that, in no house > 2 people should dislike each other. > > Is there a polynomial time solution exist for this? Or is this not > solvable at all? > > -- > 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. > > -- Amit Jaspal. Men do less than they ought, unless they do all they can -- 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] A Graph Problem
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] A Graph Problem
There are n persons. You are provided with a list of ppl which each person does not like. Determine the minm no. of houses required such that, in no house 2 people should dislike each other. Is there a polynomial time solution exist for this? Or is this not solvable at all? -- 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] 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 --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
