Joey doesn't share food

Joey doesn't share food

Every friends fan know that joey loves food and monica loves to cook. So, on a occassion of thanksgiving monica made N types of food containing exactly 6 ingredients each. Monica is an excellent cook so she can cook food by adding any ingredient at any order. All ingredients contains protein on the scale of 1 to 10^6. Now, Chandler invented the fun game where everyone needs to find the successive protein rate in all N food of the ingredient on the top(6th ingredient is on top). Ross being the most curious wants to finish this game before dinner, so he wants your help to complete the task.


First line consists of T test cases. First line of every test case consists of N. Next N lines contains the 6 integers each.



Let's understand with the example.
4
1 2 3 4 5 6
2 3 4 5 6 7
3 4 5 6 7 10
4 5 6 7 8 9
By the use of hashing we can make a graph.
1->0
2->0 1
3->0 1 2
4->0 1 2 3
5->0 1 2 3
6->0 1 2 3
7->1 2 3
8->3
9->3
10->2

Now apply dfs for every number to find the max successive it can go. 
Use of Bipartite Matching and Ford-Fulkerson.

Complexity-> It is done for every number so N. and by dfs it can at max of N numbers so, N * N. But it will be always less than N^2. But in worst case O(N^2).

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1000010;

long long iter, was[MAX];
int pa[MAX], pb[MAX];
vector <int> g[MAX];
int a[MAX][7];

bool dfs(int v) {

  was[v] = iter;

  for (int j : g[v]) {
    if (pb[j] == -1) {
      pa[v] = j;
      pb[j] = v;
      return true;
    }
  }


  for (int j : g[v]) {
    if (was[pb[j]] != iter) {
      if (dfs(pb[j])) {
        pa[v] = j;
        pb[j] = v;
        return true;
      }
    }
  }

  return false;
}

int main() {
  int tt;
  scanf("%d", &tt);
  for (int qq = 1; qq <= tt; qq++) {
    int n;
    scanf("%d", &n);

    for (int i = 0; i < MAX; i++) {
      g[i].clear();
    }

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < 6; j++) {
        scanf("%d", a[i] + j);
        g[a[i][j]].push_back(i);
      }
    }

    for (int i = 0; i < MAX; i++) {
      random_shuffle(g[i].begin(), g[i].end());
    }

    for (int i = 0; i < MAX; i++) {
      pa[i] = -1;
      was[i] = -1;
    }

    for (int j = 0; j < n; j++) {
      pb[j] = -1;
    }

    int ans = 0;
    int rr = 0;
    iter = 0;

    for (int ll = 1; ll < MAX; ll++) {
      rr = max(rr, ll - 1);
      while (true) {
        iter++;
        if (dfs(rr + 1)) {
          rr++;
        } else {
          break;
        }
      }

      ans = max(ans, rr - ll + 1);

      if (pa[ll] != -1) {
        pb[pa[ll]] = -1;
        pa[ll] = -1;
      }

    }
    printf("%d\n", ans);
  }
  return 0;
}