Advertisement
Josif_tepe

Untitled

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