O(n) algorithm to find a “publisher” in a social network -

i asked question how find "publisher" in social network. suppose (simplified) social network has "following" relationship between 2 users , 1 cannot follow himself. define "publisher" user followed other users not follow anyone.

more specifically, given such social network graph in format of adjacency matrix, nxn bool matrix, cell[i,j] indicates whether or not user follows user j. how find out publisher.

what can see there @ 1 publisher exist.(it's easy prove: since publisher followed else, else follows @ least 1 user, not publisher). come naive solution: first scan column column, if there true column j (except cell[j,j] of course), scan row[j] make sure it's false.

obviously, performance o(n^2) naive algorithm cause scan whole matrix. however, told there o(n) solution. kind of stuck @ o(n). hints?

if data presented adjacency matrix, can proceed follows. start checking entry (1,2) in matrix. if 1 follows 2 1 not publisher, , if 1 not follow 2 2 not publisher. remove whoever not publisher (1 or 2) , let x remaining node. check entry (x,3) in matrix. either x not publisher or 3 not publisher. remove whoever not publisher , add node 4 , repeat. after have repeated process n nodes, left 1 candidate publisher. can check row , column candidate verify true publisher. total running time o(n) entire algorithm, though adjacency matrix has size n^2.