Also known as the “mayor problem” or “mayor puzzle”, this is a directed graph puzzle where a group of people have single directed relationships. That is person A knows person B, but person B may or may not know person A. The puzzle is to find a person in this group that everyone knows, but he only knows himself. To phrase it differently, this breaks down to two conditions:
1) person C must be known by everyone, and
2) person C must know no one but himself.
The obvious solution is to compare every member to every other member and that would give you a solution that runs in O(n^2). If we’re given a function called ‘Knows’ that accepts two arguments (and returns in O(1)), we can write a PHP function like this:
function theSlowMayor(){
$townSize = 5;
$candidates = array();
// 1) The mayor must know no one.
for( $i=0; $i < $townSize; $i++ ){
for( $j=0; $j < $townSize; $j++ ){
if( Knows($i,$j) && $i != $j )
break;
if( $j == $townSize - 1)
$candidates[] = $i;
}
}
// 2) Every one must know the mayor.
foreach( $candidates as $c ){
for( $i=0; $i<$townSize; $i++ ){
if( !Knows($i,$c) && $i != $c )
break;
if( $i == $townSize - 1 )
return $c;
}
}
}
While this may work, it's hardly ideal. We need a way to disqualify a candidate with every iteration over the list. This way, with one pass over the list we can remove anyone that is not the mayor / celebrity.
function theMayor(){
$townSize = 5;
$mayor_set = array();
for( $i=0; $i < $townSize; $i++ )
$mayor_set[] = $i;
for( $i=0; $i < count($mayor_set); $i++ ){
for( $j=0; $j < count($mayor_set); $j++ ){
if( $i == $j )
continue;
if( Knows($i, $j) ) {
// 1) The mayor must know no one.
unset($mayor_set[$i]);
} else {
// 2) Every one must know the mayor.
// if i doens't know j, then j can't be the mayor
unset($mayor_set[$j]);
}
}
}
return array_shift($mayor_set);
}
Reading the algorithmic complexity of this code can be tricky. Seeing a nested for loop usually means O(n^2), but in this case we are eliminating one element from the $mayor_set with every iteration so we only require one pass to find the mayor. This does require enough memory to hold the a list of identifiers for the entire town, so this algorithm may not work on very large data sets.
This question comes from the Cormin Book where 22.1-6 states:
When an adjacency-matrix representation is used, most graph algorithms require time O(V^2), but there are some exceptions. To show that determining whether a directed graph G contains a universal sink - vertex with in-degree |V|-1 and out-degree 0 - can be determined in O(V), given an adjacency matrix for G.
If you want to test the functions above, you can use this sample 'Knows' function:
function Knows($i, $j){
$set = array();
$set[] = array(1, 0, 1, 0, 1);
$set[] = array(0, 1, 1, 1, 0);
$set[] = array(0, 0, 1, 0, 0);
$set[] = array(1, 1, 1, 1, 1);
$set[] = array(0, 1, 1, 0, 1);
return $set[$i][$j];
}