[algogeeks] Fwd: Graph problem - cut vertex
how to find all cut vertexes in a given graph ?? -- 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
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 jagadish1...@gmail.com 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.
[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.
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] Re: Graph problem
On 11/30/07, John [EMAIL PROTECTED] wrote:
Given a DAG and two vertices s and t , give a linear time number of
paths between s and t in G.
How does topological sort help in finding the same ?
Hi Joh,
you can do a dynamic programming algorithm Your state is S[x] = number
of path going from s to x, s is the initial vertex. It's easy to see
that equation holds :
S[x] = sum { S[v], for all v neighbor of x }
Think about base cases and make a memorized function to get the answer.
Hope this help,
Caio
--~--~-~--~~~---~--~~
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: Graph problem
Just to clarify, you are looking for a linear time algorithm that counts all s-t paths (not necessarily disjoint) in a DAG? On Nov 29, 10:35 pm, John [EMAIL PROTECTED] wrote: Given a DAG and two vertices s and t , give a linear time number of paths between s and t in G. How does topological sort help in finding the same ? --~--~-~--~~~---~--~~ 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: Graph problem
Just use BFS, its running time is O(V+E). In our case, there's no cycle in DAG so, E=V-1 always. John wrote: Given a DAG and two vertices s and t , give a linear time number of paths between s and t in G. How does topological sort help in finding the same ? --~--~-~--~~~---~--~~ 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: graph problem : i need help
Not sure about what's wrong with your code is but the answer to the problem is Warshall's algorithm for graph closure. Just to brief, say we are given the adjacency matrix A[1] where A[1][i] [j] = 1 if there's an edge from i to j. Let A[k][i][j] be the the number of paths from i to j passing through only vertices numbered from 1..k. Then note that A[k][i][j] = A[k-1][i][j] + A[k-1][i][k] * A[k-1][k] [j]. i.e., the number of paths from i to j passing through only vertices numbered 1...k is equal to number of paths from i to k passing through vertices numbered 1...k-1 PLUS number of paths from i to k (with vertices 1...k-1) and k to j (with vertices 1..k-1). What we want is the A[n] matrix which has the number of paths between every pair of vertices. But by any chance A[n][i][i] 0 for any 'i' that means there's a loop and i is a part of that loop. So this means there are infinite ways to reach i from i and hence infinite ways to reach from i to j if there's a way to reach from i to j. Hope that helps. I will paste the code once I am done with it. --~--~-~--~~~---~--~~ 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: graph problem : i need help
Here's the code.
void Closure(int **a, int v) //a is the given adjacency matrix and v
is the number of vertices
{
int **t1 = new int*[v];
int **t2 = new int*[v];
for(int i = 0; i v; ++i)
{
t1[i] = new int[v];
t2[i] = new int[v];
for(int j = 0; j v; ++j)
t1[i][j] = a[i][j];
}
int **p1 = t1, **p2 = t2, **t;
for(int k = 0; k v; ++k)
{
for(int i = 0; i v; ++i)
for(int j = 0; j v; ++j)
p2[i][j] = p1[i][j] + (p1[i][k] * p1[k][j]);
//to count the number
of paths
//swap p1, p2
t = p1; p1 = p2; p2 = t;
}
//if p1[i][i] != 0, then there is a path from i to i itself which is
a loop so there are infinite paths from i to j if there's one path
from i to j
for(int i = 0; i v; ++i)
{
if (p1[i][i] != 0)
{
p1[i][i] = -1; //-1 means loop and hence infinite paths
for(int j = 0; j v; ++j)
p1[i][j] = p1[i][j] ? -1 : p1[i][j];
}
}
for(int i = 0; i v; ++i)
for(int j = 0; j v; ++j)
a[i][j] = p1[i][j];
//array a now has the number of paths
}
--~--~-~--~~~---~--~~
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: Graph Problem
Can it be a solution? At first let us think all the edges are undirected. That is if a adjacent to b then both a-b and b-a are present. then we discard a-b if a is the current vertex with maximum outdegree and b is its adjacent with minimum outdegree and b-a is present we continue it again and again untill all the extra edges are removed. will it work? --~--~-~--~~~---~--~~ 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: Graph Problem
Ohh, sorry to have missed that information. Consider minimizing the maximum out-degree. On May 16, 5:04 pm, Rajiv Mathews [EMAIL PROTECTED] wrote: Could you please explain the question. Typically in a directed graph we talk of in-degree and out-degree for a vertex. So is the question then to minimize the maximum of these in all vertices of the graph? If so what operations are permitted? On 5/16/07, pramod [EMAIL PROTECTED] wrote: Here's a graph problem. We are given a directed graph. We are allowed to change the directions of the edges. Our aim is to minimize the maximum degree in the graph. How do we achieve this? One way is to take the vertex with maximum degree, and take another vertex with least degree reachable from this max-degree vertex and then reverse all the edges' direction along the path. Now the questions with this approach are (1) how do we prove that this will lead to the optimal-graph in the sense, can we get a graph such that it's maximum degree is the best possible? (2) What's the time complexity, is it bound tightly? (3) Is there any better way? Thanks -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ 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: Graph Problem
Could you please explain the question. Typically in a directed graph we talk of in-degree and out-degree for a vertex. So is the question then to minimize the maximum of these in all vertices of the graph? If so what operations are permitted? On 5/16/07, pramod [EMAIL PROTECTED] wrote: Here's a graph problem. We are given a directed graph. We are allowed to change the directions of the edges. Our aim is to minimize the maximum degree in the graph. How do we achieve this? One way is to take the vertex with maximum degree, and take another vertex with least degree reachable from this max-degree vertex and then reverse all the edges' direction along the path. Now the questions with this approach are (1) how do we prove that this will lead to the optimal-graph in the sense, can we get a graph such that it's maximum degree is the best possible? (2) What's the time complexity, is it bound tightly? (3) Is there any better way? Thanks -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ 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] 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 -~--~~~~--~~--~--~---
