This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub crackersamdjam/Codebook
#pragma once #include "../../utils/template.h" /** * @brief Hopcroft Karp */ struct hopcroft_karp{ vector<vector<int>> adj; vector<int> btoa; bool dfs(int cur, int L, vector<int>& A, vector<int>& B){ if(A[cur] != L) return 0; A[cur] = -1; for(int u: adj[cur]){ if(B[u] == L+1){ B[u] = 0; if(btoa[u] == -1 or dfs(btoa[u], L+1, A, B)) return btoa[u] = cur, 1; } } return 0; } vector<pair<int, int>> run(){ vector<int> A(adj.size()), B(btoa.size()), cur, nx; // A stores the levels of left side nodes, B stores the levels of right side nodes while(1){ fill(all(A), 0); fill(all(B), 0); cur.clear(); // Unmatched A nodes are sources of first layer for(int i: btoa) if(~i) A[i] = -1; for(int i = 0; i < size(adj); i++) if(A[i] == 0) cur.push_back(i); /// Find all layers using BFS for(int lay = 1;; lay++){ bool islast = 0; nx.clear(); for(int i: cur){ for(int j: adj[i]){ if(btoa[j] == -1){ B[j] = lay; islast = 1; } else if(btoa[j] != i and !B[j]){ B[j] = lay; nx.push_back(btoa[j]); } } } if(islast) break; if(nx.empty()) goto out; for(int i: nx){ A[i] = lay; } swap(cur, nx); } /// Use DFS to scan for augmenting paths for(int i = 0; i < size(adj); i++) dfs(i, 0, A, B); } out:; vector<pair<int, int>> matching; for(int i = 0; i < size(btoa); i++){ if(~btoa[i]){ matching.emplace_back(btoa[i], i); } } return matching; } };
#line 1 "content/utils/template.h" /** * @brief My starter code */ #include <bits/stdc++.h> #define all(x) (x).begin(), (x).end() #define makeunique(x) (x).erase(unique((x).begin(), (x).end()), (x).end()); #ifdef LOCAL template<typename T> void pr(T a){std::cerr<<a<<std::endl;} template<typename T, typename... Args> void pr(T a, Args... args){std::cerr<<a<<' ',pr(args...);} #else template<typename... Args> void pr(Args... args){} #endif using namespace std; using ll = long long; using pii = pair<int, int>; #line 3 "content/graph/flow/hopcroft_karp.h" /** * @brief Hopcroft Karp */ struct hopcroft_karp{ vector<vector<int>> adj; vector<int> btoa; bool dfs(int cur, int L, vector<int>& A, vector<int>& B){ if(A[cur] != L) return 0; A[cur] = -1; for(int u: adj[cur]){ if(B[u] == L+1){ B[u] = 0; if(btoa[u] == -1 or dfs(btoa[u], L+1, A, B)) return btoa[u] = cur, 1; } } return 0; } vector<pair<int, int>> run(){ vector<int> A(adj.size()), B(btoa.size()), cur, nx; // A stores the levels of left side nodes, B stores the levels of right side nodes while(1){ fill(all(A), 0); fill(all(B), 0); cur.clear(); // Unmatched A nodes are sources of first layer for(int i: btoa) if(~i) A[i] = -1; for(int i = 0; i < size(adj); i++) if(A[i] == 0) cur.push_back(i); /// Find all layers using BFS for(int lay = 1;; lay++){ bool islast = 0; nx.clear(); for(int i: cur){ for(int j: adj[i]){ if(btoa[j] == -1){ B[j] = lay; islast = 1; } else if(btoa[j] != i and !B[j]){ B[j] = lay; nx.push_back(btoa[j]); } } } if(islast) break; if(nx.empty()) goto out; for(int i: nx){ A[i] = lay; } swap(cur, nx); } /// Use DFS to scan for augmenting paths for(int i = 0; i < size(adj); i++) dfs(i, 0, A, B); } out:; vector<pair<int, int>> matching; for(int i = 0; i < size(btoa); i++){ if(~btoa[i]){ matching.emplace_back(btoa[i], i); } } return matching; } };