[UVa] 11419 - SAM I AM

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 11419 - SAM I AM
Source            : UVa Online Judge
Category          : Graph Theory
Algorithm         : Maximum Bipartite Matching 2D, Kuhns Algorithm
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
static const int maxn = 5e3 + 5;
 
vector <int> bipertite_graph[maxn];  // row -> column
int row, column, k;
 
int visrow[maxn], viscolumn[maxn];
int Left[maxn], Right[maxn], seen[maxn];
 
inline bool kuhn(int r)
{
      visrow[r] = 1;
      for (int c : bipertite_graph[r])
      {
            if (viscolumn[c] == 0)
            {
                  viscolumn[c] = 1;
                  if (Right[c] == -1 || kuhn(Right[c]))
                  {
                        Right[c] = r;
                        Left[r] = c;
                        return 1;
                  }
            }
      }
      return false;
}
 
inline int bpm()
{
      for (int i = 0; i < maxn; i++)
      {
            Left[i] = Right[i] = -1;
            visrow[i] = viscolumn[i] = 0;
      }
      int match = 0;
      for (int i = 1; i <= row; i++)
      {
            for (int j = 0; j < maxn; j++) viscolumn[j] = 0;
            if (kuhn(i)) match++;
      }
      return match;
}
 
int main()
{
      //freopen("in.txt", "r", stdin);
 
      while (cin >> row >> column >> k)
      {
            if (row == 0 && column == 0 && k == 0) break;
            for (int i = 0; i < k; i++)
            {
                  int x, y;
                  cin >> x >> y;
                  y += row;
                  bipertite_graph[x].push_back(y);
            }
            int maximum_bipertite_matching = bpm();
            printf("%d", maximum_bipertite_matching);
 
            for (int i = 0; i < maxn; i++) visrow[i] = viscolumn[i] = 0;
            for (int i = 1; i <= row; i++) if (Left[i] == -1) kuhn(i);
 
            for (int i = 1; i <= row; i++)
            {
                  if (!visrow[i]) printf(" r%d", i);
            }
            for (int i = row+1; i <= row+column; i++)
            {
                  if (viscolumn[i]) printf(" c%d", i - row);
            }
            puts("");
 
            for (int i = 0; i < maxn; i++) bipertite_graph[i].clear();
      }
}