Isnt it running DFS on every node?
1) Pick any node in the graph say n
2) With n as root, run DFS. While running DFS, if you visit node x, mark
M[n,x]=1 and M[x,n]=1 (since its unidirected graph, M[i,j] will be equal
to M[j,i] for any j,i) .
The running time is O(k) where k is the number of nodes
Isnt it running DFS on every node?
1) Pick any node in the graph say n
2) With n as root, run DFS. While running DFS, if you visit node x, mark
M[n,x]=1 and M[x,n]=1 .
The running time is O(k+E) [not k, you are forgetting the case when E !=
O(n)] .Also have a hash finished[n]=true.
3) Repeat steps
On Tue, Nov 24, 2009 at 1:48 PM, Arun arunm...@gmail.com wrote:
Isnt it running DFS on every node?
1) Pick any node in the graph say n
2) With n as root, run DFS. While running DFS, if you visit node x, mark
M[n,x]=1 and M[x,n]=1 (since its unidirected graph, M[i,j] will be equal
to M[j,i]
it is what the question says..
and that's why the question is here
right?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
You just need to run DFS once. It will give you all the connected
components. So it is indeed O(n+e)
On Tue, Nov 24, 2009 at 2:43 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
Isnt it running DFS on every node?
1) Pick any node in the graph say n
2) With n as root, run DFS. While running
COMPUTE (x,y) {
if(matrix[x][y] != EMPTY) return matrix[x][y];
for all k in 1:N
if(COMPUTE(x,k)COMPUTE(k,y)) matrix[x][y]=1; EXIT
endfor
matrix[x][y]=0;
}
CLOSURE (M){ //M is the matrix
for all i,j s.t matrix[x][y]=EMPTY
Hi,
On Tue, Nov 24, 2009 at 3:09 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
it is what the question says..
and that's why the question is here
right?
Could you clarify what the question asks please. Does it want you to get the
connected components? Or does it want you propose a data
COMPUTE (x,y) {
if(matrix[x][y] != EMPTY) return matrix[x][y];
for all k in 1:N
if(COMPUTE(x,k)COMPUTE(k,y)) matrix[x][y]=matrix[y][x]=1; EXIT
endfor
matrix[x][y]=0;
}
CLOSURE (M){ //M is the matrix
for all i,j s.t matrix[x][y]=EMPTY
You are given a graph G.
if there exists a path from ai to aj in G, then store in matrix
CLOSUREMATRIX[i][j]=1
You have to find connectivity between all pairs.
is it clear now?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
A nice problem that i encountered :
In O(n) search for a value x in a sorted NxN matrix.
Definition of sorted matrix: All rows and all columns are sorted in
ascending order.
So thought of sharing ..
Rohit Saraf
Sophomore
Computer Science and Engineering
IIT Bombay
--
You received this
Hi,
On Tue, Nov 24, 2009 at 6:38 PM, Ankur ankuraror...@gmail.com wrote:
What would be the best algorithm for the undermentioned problem.
Implement method PrintFamilyTree() that prints out the Name and
Generation of the tree
Output should resemble
Name: Jan Generation:0
Name: Mike
On Tue, Nov 24, 2009 at 3:21 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
@aditya: If you run DFS once.. you can in O(1) decide whether a point is
connected to the root of dfs tree.
but not with other points.
It is an undirected graph right? So, you can go from node A to
But then ..
think..
for every two pairs of nodes you have to check whether both are connected to
root and then you will say yes/no.
And you will have to do this for all disjoint components.
It's right but not O(n^2).
--
You received this message because you are subscribed to the Google Groups
Start from top right or bottom left corner and move according if the element
to be searched is lesser or greater than current.
--Koushik C
Pablo Picassohttp://www.brainyquote.com/quotes/authors/p/pablo_picasso.html
- Computers are useless. They can only give you answers.
On Tue, Nov 24, 2009
Hi,
What I am trying to say is this.
a. Do a DFS on the given graph G to get connected components C1...Ck
b. Consider Ci
(i) I claim that every pair of nodes in the connected component is
connected to every other node in the same connected component (say you have
arbitrary points A,B in Ci,
How can i find size of an object in java
plsss answer asap
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
measure jvm memory usage before/after creating ur object; but it is not
assured to give the correct size(gc).
or u can use a premain agent.
On Wed, Nov 25, 2009 at 12:37 AM, Abhijeet Kumar
abhijeet.k.s...@gmail.comwrote:
How can i find size of an object in java
plsss answer asap
--
You
as long as it is an undirected graph;simple dfs would suffice!
On Tue, Nov 24, 2009 at 10:13 PM, Rohit Saraf
rohit.kumar.sa...@gmail.comwrote:
But then ..
think..
for every two pairs of nodes you have to check whether both are connected
to root and then you will say yes/no.
And you will
On Tue, Nov 24, 2009 at 10:46 PM, Rohit Saraf
rohit.kumar.sa...@gmail.comwrote:
i had already understood what you claimed
But MY CLAIM: every pair of nodes in the connected component is connected
to every other node in the same connected component. U CANNOT UPDATE ALL THE
PAIRS AS EASILY AS
void PrintFamilyTree(const short generation)
{
printf(Name : %s Generation = %d\n, m_Name.c_str(),generation);
vectorHuman*::iterator it;
for (it = this.begin(); it this.end() ;it++)
{
it-PrintFamilyTree(generation+1);
}
}
On Tue, Nov 24, 2009 at 9:20 PM, Aditya Shankar
20 matches
Mail list logo
