Show that determining whether a directed graph G contains a universal sink – a vertex of indegree |V| - 1 and outdegree 0 – can be determined in time O(V ).

How many sinks could a graph have?

• 0 or 1

How can we determine whether a given vertex u is a universal sink?

• The u row must contain 0’s only

• The u column must contain 1’s only

• A[u][u]=0

How long would it take to determine whether a given vertex u is a universal sink?

• O(V) time 

UNIVERSAL-SINK(A)

let A be |V|x|V|

i=j=1

while i<=|V| and j<=|V| 

      if a<sub>ij =1
          then i=i+1;
          else j=j+1;
if i>|V|
   return "no universal sink";
if ISSINK(A,i) =false
   return "no universal sink";
else 
  return i;

ISSINK(A,k)</sub>

let A be |V|x|V|
for j=1 to |V|
   if a_kj=1 or (a_jk=0 and j!=k)
       return false
return true