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)` :)

## No comments :

Post a Comment