Advertisement
Josif_tepe

Untitled

Dec 26th, 2022
909
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.12 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <cstring>
  5. #include <queue>
  6. #include <algorithm>
  7. using namespace std;
  8. const int maxn = 150;
  9. int graph[maxn][maxn];
  10. bool visited[maxn];
  11. int match[maxn];
  12. int n;
  13. bool dfs(int node) {
  14.     for(int i = 0; i < maxn; i++) {
  15.         if(graph[node][i] == 1 and !visited[i]) {
  16.             visited[i] = true;
  17.             if(match[i] == -1 or dfs(match[i])) {
  18.                 match[i] = node;
  19.                 return true;
  20.             }
  21.         }
  22.     }
  23.     return false;
  24. }
  25. int maximum_bipartite_matching() {
  26.     memset(match, -1, sizeof match);
  27.     int result = 0;
  28.     for(int i = 0; i < n; i++) {
  29.         memset(visited, false, sizeof visited);
  30.         if(dfs(i) == true) {
  31.             result++;
  32.         }
  33.     }
  34.     return result;
  35. }
  36. int main() {
  37.    int  m;
  38.     cin >> n >> m;
  39.     memset(graph, 0, sizeof graph);
  40.     for(int i = 0; i < m; i++) {
  41.         int a, b;
  42.         cin >> a >> b;
  43.         graph[a][b] = 1;
  44.     }
  45.     cout << maximum_bipartite_matching() << endl;
  46.     return 0;
  47. }
  48. /*
  49.  10 9
  50.  1 6
  51.  1 9
  52.  1 10
  53.  2 6
  54.  2 7
  55.  3 7
  56.  4 8
  57.  4 9
  58.  5 10
  59.  */
  60.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement