Graph Matching

Hopcroft craft sqrt(m)*n complexity may be ... 

#include<bits/stdc++.h>
using namespace std;

const int N = 3e5 + 9;

struct HopcroftKarp {
  static const int inf = 1e9;
  int n;
  vector<int> l, r, d;
  vector<vector<int>> g;
  HopcroftKarp(int _n, int _m) {
    n = _n;
    int p = _n + _m + 1;
    g.resize(p);
    l.resize(p, 0);
    r.resize(p, 0);
    d.resize(p, 0);
  }
  void add_edge(int u, int v) {
    g[u].push_back(v + n); //right id is increased by n, so is l[u]
  }
  bool bfs() {
    queue<int> q;
    for (int u = 1; u <= n; u++) {
      if (!l[u]) d[u] = 0, q.push(u);
      else d[u] = inf;
    }
    d[0] = inf;
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (auto v : g[u]) {
        if (d[r[v]] == inf) {
          d[r[v]] = d[u] + 1;
          q.push(r[v]);
        }
      }
    }
    return d[0] != inf;
  }
  bool dfs(int u) {
    if (!u) return true;
    for (auto v : g[u]) {
      if(d[r[v]] == d[u] + 1 && dfs(r[v])) {
        l[u] = v;
        r[v] = u;
        return true;
      }
    }
    d[u] = inf;
    return false;
  }
  int maximum_matching() {
    int ans = 0;
    while (bfs()) {
      for(int u = 1; u <= n; u++) if (!l[u] && dfs(u)) ans++;
    }
    return ans;
  }
};
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m, q;
  cin >> n >> m >> q;
  HopcroftKarp M(n, m);
  while (q--) {
    int u, v;
    cin >> u >> v;
    M.add_edge(u, v);
  }
  cout << M.maximum_matching() << '\n';
  return 0;
}

max bipartite matching ... 

kuhn runs for O(n*m) or O(v^3) maybe... 

bool kuhn(int u)
{
    for(int v=1; v<=m; ++v)
    {
        if(di[u][v] and !vis[v])
        {
            vis[v]=1 ;
            if(p[v]==-1 or kuhn(p[v]))
            {
                p[v]=u ;
                return 1 ;
            }
        }
    }
    return 0 ;
}
 
void max_match()
{
    memset(p,-1,sizeof(p)) ;
    for(int i=1; i<=m; ++i)
    {
        memset(vis,0,sizeof(vis)) ;
        kuhn(i) ;
    }
    for(int i=1; i<=m; ++i)
    {
        if(p[i]!=-1)
        {
            sub[p[i]]=i ;
        }
    }
}


/*

/// non bipartite matching ... a 
/// O(v^3) maybe . also known as edmonds maybe .  
/// https://open.kattis.com/problems/translatorsdinner
 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#include <functional> // for less
#include <iostream>
#define   MP             make_pair
#define   PB             push_back
#define   EB             emplace_back
#define   nn             '\n'
#define   endl           '\n'
#define   IOS            ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define   UNIQUE(vec)    vec.resize(distance(vec.begin(),unique(vec.begin(),vec.end()))) ;
#define   all(vec)       vec.begin(),vec.end()
#define   int            long long
#define   pii            pair<int,int>
#define   pdd            pair<double,double>
#define   ff             first
#define   ss             second

using namespace std ;

typedef long long LL ;

const int MOD=1e9+7,Base=998244353 ;
const int N=1e6+7 ;
const int oo=1LL*1000*1000*1000*1000*1000*1000+7LL ;
const double pie=acos(-1.0) ;
const double EPS=1e-9 ;

int n , test ;

vector<int> Blossom(vector<vector<int>>& graph) {
  int n = graph.size(), timer = -1;
  vector<int> mate(n, -1), label(n), parent(n),
              orig(n), aux(n, -1), q;
  auto lca = [&](int x, int y) {
    for (timer++; ; swap(x, y)) {
      if (x == -1) continue;
      if (aux[x] == timer) return x;
      aux[x] = timer;
      x = (mate[x] == -1 ? -1 : orig[parent[mate[x]]]);
    }
  };
  auto blossom = [&](int v, int w, int a) {
    while (orig[v] != a) {
      parent[v] = w; w = mate[v];
      if (label[w] == 1) label[w] = 0, q.push_back(w);
      orig[v] = orig[w] = a; v = parent[w];
    }
  };
  auto augment = [&](int v) {
    while (v != -1) {
      int pv = parent[v], nv = mate[pv];
      mate[v] = pv; mate[pv] = v; v = nv;
    }
  };
  auto bfs = [&](int root) {
    fill(label.begin(), label.end(), -1);
    iota(orig.begin(), orig.end(), 0);
    q.clear();
    label[root] = 0; q.push_back(root);
    for (int i = 0; i < (int)q.size(); ++i) {
      int v = q[i];
      for (auto x : graph[v]) {
        if (label[x] == -1) {
          label[x] = 1; parent[x] = v;
          if (mate[x] == -1)
            return augment(x), 1;
          label[mate[x]] = 0; q.push_back(mate[x]);
        } else if (label[x] == 0 && orig[v] != orig[x]) {
          int a = lca(orig[v], orig[x]);
          blossom(x, v, a); blossom(v, x, a);
        }
      }
    }
    return 0;
  };
  // Time halves if you start with (any) maximal matching.
  for (int i = 0; i < n; i++)
    if (mate[i] == -1)
      bfs(i);
  return mate;
}

bool common(pii a,pii b)
{
    return (a.ff==b.ff or a.ff==b.ss or a.ss==b.ff or a.ss==b.ss) ;
}

int32_t main()
{
    IOS

    int n , m ;

    cin>>n>>m ;

    vector<pii>vec ;

    for(int i=1;i<=m;i++)
    {
        int u , v ; cin>>u>>v ; vec.push_back({u,v}) ;
    }

    vector<vector<int>>adj(m) ;

    for(int i=0;i<m;i++)
    {
        for(int j=i+1;j<m;j++)
        {
            if(common(vec[i],vec[j]))
            {
                adj[i].push_back(j) ;
                adj[j].push_back(i) ;
            }
        }
    }

    vector<int>ans=Blossom(adj) ;

    for(int i=0;i<m;i++)
    {
        if(ans[i]==-1)cout<<"impossible\n" ,  exit(0) ;
    }

    for(int i=0;i<m;i++)
        if(i>ans[i])
          cout<<i<<' '<<ans[i]<<endl ;

    return 0 ;
}
/**/