Markymark
BAN USERThat's a pretty good idea but you don't even need to do DFS.
We can do it in time O(mn) without using any excess memory.
We will change values in the original nxm 2d array of integers.
Set each component to a certain number. Then re-scan the grid and print out the indices. You could manipulate the output to be in the correct lines or you could use lists and then do it.
Start with a counter
int currentValue = 2;
Scan the grid from the top left to the bottom right and only pay attention to values that have a value > 0.
If the value at the current position == 1 check all the immediately surrounding neighbors. If any of them are a higher value than 1, set the current node's value to this higher value. Otherwise set the current node's value to currentValue and increment currentValue by 1.
Repeat.
Now we have all the clusters with a different number >=2.
All we have to do now is output the data.
The easiest thing to do would be use some memory and add the nodes to lists. But you could also manipulate the output by maybe writing to a file on a certain line based on the cluster number.
That's a very good analysis but I question your second answer. I feel the total number is unbounded because you can have multiple directed edges from vertex A to vertex B. In your example if this were sorted it would only have one edge. But really it could have 20K edges going from A to B. It really just depends on how they are arranged. Is the question over possibility?..
- Markymark November 23, 2014