CareerCup

Above poster got it mostly correct, but a little needlessly convoluted.

Two things need to be true.

1.) There should be N-1 edges;
2.) No node has more than one outgoing edge;

bool isStraightLine( bool graph[N][N] )
{
	int numEdges = 0;
	bool foundEdge = false;
	for ( int i = 0; i < N; i++ )
	{
		foundEdge = false;
		for (int j = 0; j < N; j++ )
		{
			if ( graph[i][j] )
			{
				if ( foundEdge )
				{
					return false;
				}
				foundEdge = true;
				numEdges++;				
			}
		}
	}
	if ( numEdges == N - 1 )
	{
		return true;
	}
	else 
	{
		return false;
	}
}

Your code will not work for dis connected graphs with self loop, you should also check the condition when i==j then graph[i][j] is not set.
sample test case:
100
010
001

Your code will fail for the above test case.

If the given graph is a line ,it should satisfy the following conditions:
1) Its should be connected-->for checking connectivity use dfs or bfs
2) Except starting and end vertes, all other vertex should have degree=2 with indegree=1 && outdegree=1
for starting vertex outdegree=1 && indegree=0
for end vertex indegree=1 && outdegree=0

If u assume that the it is an undirected graph, you can stop j with j <= i which will reduce the time complexity of the code by HALF :)

@kuberan actually your test will not cause it to fail, as there are 3 edges and 3 nodes, so n-1 is not adhered to.

But yes a test case such as
1 0
0 0

Will cause it to fail.

So I suppose we should check for for self-loops, and that will close taht test case.

Check for existence of eulerian path:
1. n-2 vertices should have indegree=outdegree(not necessarily 2).
2. start vertes should have indegree = outdegree-1 and end vertex should have indegree = outdegree + 1.
3. Finally check for connectivity.

seems to me all we need are three rules
1. no self connection: matrix[i][i] =0
2. check all the entry in matrix[i][j] that i<j, each row matrix[i] should have at most one entry as 1
3. the total entries that is 1 in the matrix[i][j] that i<j is n-1

Would the above three rules be suffice?

seems to me all we need are three rules
1. no self connection: matrix[i][i] =0
2. check all the entry in matrix[i][j] that i<j, each row matrix[i] should have at most one entry as 1
3. the total entries that is 1 in the matrix[i][j] that i<j is n-1

Would the above three rules be suffice?

idea and Ryans approach are correct and the rest Junk.

Do a BSF as you usually do using a queue..At a no point in time, the queue size should exceed 1, in which case, we 'll return false.

geek: BSF=Border Security Force?

geek: BSF=Border Security Force?

Both BFS and DFS should be the same..

check in degree and out degree of each node,
only 1 node has 1 out degree and doesn't have in degree
only 1 node has 1 in degree and doesn't have out degree
every other node has 1 in degree and 1 out degree

well, you can pick the first row of the matrix and locate the entry with 1, if it was the jth entry, go to the jth row and look for a 1 and continue so on till you hit a row with zero 1's.
Now take the 1st column and look for a 1, basically the same routine as above but with columns this time.
Also whenever you visit a column or a row make sure that the number of 1's in it is less than 2, if not return false

At any point of time keep a count of the jumps(row2row or col2col) you made, if the count is greater than n (basically this a check for a loop ), return false. If at the end of all the jumps the count is less than n return false (implies the straight line not complete)

In all other cases return true


P.S: the definition of number of jumps depends on how u count it. so, n might not be the appropriate bound

Every node, except the last, has only one child.

Can we try adding the row values and verify the idea of "idea" above...

1----4----2----3

Matrix | RowSum
0001 = 1
0011 = 2
0100 = 1
1100 = 2
||||
1212 <- Col Sum

No row can have sum 0
Only 2 rows can have sum = 1
The sequence of row count should be same 1212 ~ 1212
Diagonals = 0
And Symmetric Matrix

i think guys here have already discussed about the solution i'm writing. It's
O(n2). Is there any lower order solution ?
bool isStraightLine(bool edges[N][N])
{
int outEdges[n];
int inEdges[n];
for (int i =0; i < 0; i++) {
inEdges[i] = outEdges[i] = 0;
}
for (int i=0; i < N; i++) {
for(int j =0; j < N ; j++) {
outEdges[i] += edges[i][j];
inEdges[j] += edges[i][j];
}
}
bool straightLine = true;
for (int i =0; i < N; i++) {
if ((inEdges[i] > 1) || (outEdges[1] > 1)) {
straightLine = false;
break;
}
}
return straightLine;
}

i think guys here have already discussed about the solution i'm writing. It's
O(n2). Is there any lower order solution ?
bool isStraightLine(bool edges[N][N])
{
int outEdges[n];
int inEdges[n];
for (int i =0; i < 0; i++) {
inEdges[i] = outEdges[i] = 0;
}
for (int i=0; i < N; i++) {
for(int j =0; j < N ; j++) {
outEdges[i] += edges[i][j];
inEdges[j] += edges[i][j];
}
}
bool straightLine = true;
for (int i =0; i < N; i++) {
if ((inEdges[i] > 1) || (outEdges[1] > 1)) {
straightLine = false;
break;
}
}
return straightLine;
}

if( no diagonal element is 1 ) && ( every row has only one entry '1' ) && ( every column has only one entry '1' )
will implicitly guarantee that the graph in question is connected and is in straight line.