| 71 | emarked[v][w] = emarked[w][v] = true; } |
| 72 | marked[v] = true; } return q; } |
| 73 | vii max_matching(const vector<vi> &adj) { |
| 74 | vi m(size(adj), -1), ap; vii res, es; |
| 75 | rep(i,0,size(adj)) iter(it,adj[i]) es.emplace_back(i,*it); |
| 76 | shuffle(es.begin(), es.end(), rng); |
| 77 | iter(it,es) if (m[it->first] == -1 && m[it->second] == -1) |
| 78 | m[it->first] = it->second, m[it->second] = it->first; |
| 79 | do { ap = find_augmenting_path(adj, m); |
| 80 | rep(i,0,size(ap)) m[m[ap[i^1]] = ap[i]] = ap[i^1]; |
| 81 | } while (!ap.empty()); |
| 82 | rep(i,0,size(m)) if (i < m[i]) res.emplace_back(i, m[i]); |
| 83 | return res; } |
| 84 | // vim: cc=60 ts=2 sts=2 sw=2: |
nothing calls this directly
no test coverage detected