Adjecency Matrix Algorithm - "Find the Spy"
posted 13 years ago
I've got problems with a task requireing me to go through a 500x500 adjecency matrix to find a "spy" (the node that's attached to all the others, but none is attached to it). Of course, there's no problem doing it the hard way, getting a O(n^2) time complexity, but the task says there's a O(n) way of finding it. Can anyone help me on this one? Thanx in advance