aravinds86
BAN USER
Questions (1)
Comments (5)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
If we don't want to change the graph matrix, then use separate 1D array instead of using first row.
- aravinds86 March 11, 2010Comment hidden because of low score. Click to expand.
0
of 0 vote
We can do it in o(n^2) and o(1) space as follows,
consider ur matrix with 4 vertices are represented as
1 0 0 0
0 1 0 0
1 0 0 1
0 0 1 0
Now,
for row = 2 to n
for column = 1 to n
if [row][column] is 1
then set [0][column] as 1.
Now,traverse first row and see if all are set to 1, then it is connected graph.It means we can reach from any node to any other node. There shouldn't be orphan nodes.
Comment hidden because of low score. Click to expand.
0
of 0 vote
Graph is undirected
- aravinds86 March 11, 2010Comment hidden because of low score. Click to expand.
0
of 0 vote
Use Hare and tortoise alogirthm as circular linked list is nothing but loop in a linked list.
- aravinds86 February 07, 2010Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
hary, you are right. BFS or DFS with a boolean array is right answer.
- aravinds86 March 12, 2010