[Codeforces] E. Maximize Mex

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : E. Maximize Mex
Source            : Codeforces
Category          : Graph Theory
Algorithm         : Maximum Bipartite Matching, Kuhns Algorithm
Verdict           : Accepted

Implemenatation 1

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define ll             long long int  
  
static const int maxn = 5000 + 5;  
  
int students, clubs, days;  
int potential[maxn], club[maxn], leave[maxn], gone[maxn];  
vector <int> graph[maxn]; // potential --> club  
  
// Kuhn's Algorithm for Maximum Matching in directed graph  
int Left[maxn], Right[maxn], seen[maxn];  
  
bool kuhn(int u)  
{  
      if (seen[u]) return false;  
      seen[u] = 1;  
      for (int v : graph[u])  
      {  
            if (Right[v] == -1 or kuhn(Right[v]))  
            {  
                  Left[u] = v;  
                  Right[v] = u;  
                  return true;  
            }  
      }  
      return false;  
}  
  
int main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout << fixed << setprecision(15);  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      cin >> students >> clubs;  
      for (int i = 1; i <= students; i++) cin >> potential[i];  
      for (int i = 1; i <= students; i++) cin >> club[i];  
      cin >> days;  
      for (int i = 1; i <= days; i++)  
      {  
            cin >> leave[i];  
            gone[ leave[i] ] = 1;  
      }  
      for (int i = 1; i <= students; i++)  
      {  
            if (gone[i] == 0) graph[ potential[i] ].emplace_back(club[i]);  
      }  
      int mex = 0;  
      memset(Left, -1, sizeof Left);  
      memset(Right, -1, sizeof Right);  
      vector <int> maximum_mex;  
      for (int i = days; i >= 1; i--)  
      {  
            while (true)  
            {  
                  memset(seen, 0, sizeof seen);  
                  if (kuhn(mex)) ++mex;  
                  else break;  
            }  
            maximum_mex.emplace_back(mex);  
            graph[ potential[ leave[i] ] ].emplace_back(club[ leave[i] ]);  
      }  
      reverse(maximum_mex.begin(), maximum_mex.end());  
      for (int mex : maximum_mex) cout << mex << '\n';  
}  

Implementation 2

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define ll             long long int  
  
static const int maxn = 5000 + 5;  
  
int students, clubs, days;  
int potential[maxn], club[maxn], leave[maxn], gone[maxn];  
vector <int> graph[maxn]; // potential --> club  
  
// Kuhn's Algorithm for Maximum Matching in directed graph  
int match[maxn], seen[maxn];  
  
bool kuhn(int u)  
{  
      if (seen[u]) return false;  
      seen[u] = 1;  
      for (int v : graph[u])  
      {  
            //if (seen[v]) continue;  
            //seen[v] = 1;  
            if (match[v] == -1 or kuhn(match[v]))  
            {  
                  match[v] = u;  
                  return true;  
            }  
      }  
      return false;  
}  
  
int main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout << fixed << setprecision(15);  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      cin >> students >> clubs;  
      for (int i = 1; i <= students; i++) cin >> potential[i];  
      for (int i = 1; i <= students; i++) cin >> club[i];  
      cin >> days;  
      for (int i = 1; i <= days; i++)  
      {  
            cin >> leave[i];  
            gone[ leave[i] ] = 1;  
      }  
      for (int i = 1; i <= students; i++)  
      {  
            if (gone[i] == 0) graph[ potential[i] ].emplace_back(club[i]);  
      }  
      int mex = 0;  
      memset(match, -1, sizeof match);  
      vector <int> maximum_mex;  
      for (int i = days; i >= 1; i--)  
      {  
            while (true)  
            {  
                  memset(seen, 0, sizeof seen);  
                  if (kuhn(mex)) ++mex;  
                  else break;  
            }  
            maximum_mex.emplace_back(mex);  
            graph[ potential[ leave[i] ] ].emplace_back(club[ leave[i] ]);  
      }  
      reverse(maximum_mex.begin(), maximum_mex.end());  
      for (int mex : maximum_mex) cout << mex << '\n';  
}