The "empty chairs" bipartite matching algorithm

Today while browsing the TC forums I had a blast from the past. There was a time in which I didn't know what max flow or bipartite matching is, so I had to learn it. The process was difficult and long. While trying to understand max flow though, I did get some knowledge about solving bipartite matching without max flow. Or rather by a very simplified recursive logic that does max flow.

The good thing about the recursive logic is that it has a real life metaphor that makes it easy to remember and it is also very easy to implement. I am reposting this from an old topcoder forums post I wrote a long time ago. I thought it is good to have it in a more visible place:

Well, I have a logic for bipartite matching that makes an easy to remember and implement algorithm, not to mention it is fast:

This is as best as I could explain it:

int personInChair[m]; //personInChair[m] Points to the person that's currently on  chair i
bool foundChair[n]; //foundChair[i] is 1 if and only if the guy has already sit on a chair.
 
 
bool canSit[n][m]; //canSit[i][j] is true if and only if person i can sit on chair j.
 
bool alreadyTried[n]; //alreadyTried[i] is true if person i has already tried to find a new chair
 
bool findChair(int x)
// Person x will try and find a new chair...
{
    if (alreadyTried[x]) //alreadyTried just serves the purpose of
         return false;   //preventing infinite recursion and things like that
    alreadyTried[x]= true;
 
   for (int j=0; j<m; j++)
       if(canSit[x][j])
       {
           int otherGuy = personInChair[j];
           if ( otherGuy == -1)
           {
               //the sit is empty, just sit on it!
               personInChair[j] = x;
               foundChair[x] = true;
               return true;
           }
           else
           {
               //kindly ask the other guy if he can move to another chair:
               if ( findChair(otherGuy) )
               {
                   //he was able to move.
                   personInChair[j] = x;
                   foundChair[x]=true;
                   return true;
               }
               
           }
       }
    return false; //No chairs available right now.
}
 
int maximumChairs() //this will return the maximum number of people
                    // that sit on a chair.
{
    int sum=0;
    fill(personInChair,personInChair+m, -1); //nobody has sit yet.
    fill(foundChair,foundChair+n, false);    //
    while(true)
    {
        bool somethingChanged = false;
        fill(alreadyTried,alreadyTried+n, false);
        for (int i=0; i<n; i++) //Everybody should try to find a chair.
           if(! foundChair[i] )
           {
               if(findChair[i])
               {
                   somethingChanged=true;
                   sum++;
               }
           }
        
        if(!somethingChanged)
            break;
        
    }
 
    return sum;
}

I think that when I came up with that algorithm it was based on code I've seen from red coders. The chair metaphor makes it easy to remember. I wonder if this algorithm has a name / original author or if it is something that merely materialized in programming competitions out of need.

Anyway, it is not that fast. It is `O(n^3)` :)