Advertisement
Josif_tepe

Untitled

Feb 3rd, 2023
958
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <cstring>
  4. #include <stack>
  5. #include <fstream>
  6. using namespace std;
  7. typedef long long ll;
  8. const int maxn = 667;
  9. bool graph[maxn][maxn];
  10. bool visited[maxn];
  11. int match[maxn];
  12. int n, k;
  13.  
  14. bool dfs(int node) {
  15.     for(int i = 0; i < n; i++) {
  16.         if(graph[node][i] and !visited[i]) {
  17.             visited[i] = true;
  18.            
  19.             if(match[i] == -1 or dfs(match[i])) {
  20.                 match[i] = node;
  21.                 return true;
  22.             }
  23.         }
  24.     }
  25.     return false;
  26. }
  27. int maximum_bipartite_matching() {
  28.     memset(match, -1, sizeof match);
  29.     int result = 0;
  30.    
  31.     for(int i = 0; i < n; i++) {
  32.         memset(visited, false, sizeof visited);
  33.         if(dfs(i)) {
  34.             result++;
  35.         }
  36.     }
  37.     return result;
  38. }
  39. int main() {
  40.     ios_base::sync_with_stdio(false);
  41.     cin >> n >> k;
  42.     memset(graph, true, sizeof graph);
  43.     for(int i = 0; i < k; i++) {
  44.         int a, b;
  45.         cin >> a >> b;
  46.         a--; b--;
  47.         graph[a][b] = false;
  48.        
  49.     }
  50.     cout << maximum_bipartite_matching() << endl;
  51.     return 0;
  52. }
  53.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement