fork download

copy

template <unsigned int MAXN>
struct GeneralMatching {
  array<int, MAXN + 1> visited, parent, origin, match, aux;
  int N;
 
  array<vector<int>, MAXN + 1> graph;
  queue<int> que;
 
  void add_edge(int u, int v) {
    graph[v].push_back(u);
    graph[u].push_back(v);
  }
 
  void init(int n) {
    N = n;
    for (int i = 0; i <= n; ++i) {
      graph[i].clear();
      match[i] = aux[i] = parent[i] = 0;
    }
  }
 
  void augment(int u, int v) {
    int parent_v = v, next_v;
    do {
      parent_v = parent[v];
      next_v = match[parent_v];
      match[v] = parent_v;
      match[parent_v] = v;
      v = next_v;
    } while (u != parent_v);
  }
 
  int lca(int u, int v) {
    static int label = 0;
    ++label;
    while (!v || aux[v] != label) {
      if (v) {
        aux[v] = label;
        v = origin[parent[match[v]]];
      }
      swap<int>(u, v);
    }
    return v;
  }
 
  void blossom(int v, int w, int a) {
    while (origin[v] != a) {
      parent[v] = w;
      w = match[v];
      if (visited[w] == 1) {
        que.push(w);
        visited[w] = 0;
      }
      origin[v] = origin[w] = a;
      v = parent[w];
    }
  }
 
  bool bfs(int u) {
    fill(visited.begin() + 1, visited.begin() + 1 + N, -1);
    iota(origin.begin() + 1, origin.begin() + 1 + N, 1);
    que = queue<int>();
    que.push(u);
    visited[u] = 0;
    while (!que.empty()) {
      int v = que.front();
      que.pop();
      for (int x : graph[v]) {
        if (visited[x] == -1) {
          parent[x] = v;
          visited[x] = 1;
          if (!match[x]) {
            augment(u, x);
            return true;
          }
          que.push(match[x]);
          visited[match[x]] = 0;
        } else if (visited[x] == 0 && origin[v] != origin[x]) {
          int a = lca(origin[v], origin[x]);
          blossom(x, v, a);
          blossom(v, x, a);
        }
      }
    }
    return false;
  }
 
  int Match() {
    int ans = 0;
    // find random matching (not necessary, constant improvement)
    vector<int> V(N - 1);
    iota(V.begin(), V.end(), 1);
    shuffle(V.begin(), V.end(), mt19937(0x94949));
    for (auto x : V)
      if (!match[x]) {
        for (auto y : graph[x]) {
          if (!match[y]) {
            match[x] = y;
            match[y] = x;
            ++ans;
            break;
          }
        }
      }
    for (int i = 1; i <= N; ++i) {
      if (!match[i] && bfs(i)) ++ans;
    }
    return ans;
  }
};

prog.cpp:3:3: error: ‘array’ does not name a type
   array<int, MAXN + 1> visited, parent, origin, match, aux;
   ^~~~~
prog.cpp:6:3: error: ‘array’ does not name a type
   array<vector<int>, MAXN + 1> graph;
   ^~~~~
prog.cpp:7:3: error: ‘queue’ does not name a type
   queue<int> que;
   ^~~~~
prog.cpp: In member function ‘void GeneralMatching<MAXN>::add_edge(int, int)’:
prog.cpp:10:5: error: ‘graph’ was not declared in this scope
     graph[v].push_back(u);
     ^~~~~
prog.cpp: In member function ‘void GeneralMatching<MAXN>::init(int)’:
prog.cpp:17:7: error: ‘graph’ was not declared in this scope
       graph[i].clear();
       ^~~~~
prog.cpp:18:7: error: ‘match’ was not declared in this scope
       match[i] = aux[i] = parent[i] = 0;
       ^~~~~
prog.cpp:18:18: error: ‘aux’ was not declared in this scope
       match[i] = aux[i] = parent[i] = 0;
                  ^~~
prog.cpp:18:27: error: ‘parent’ was not declared in this scope
       match[i] = aux[i] = parent[i] = 0;
                           ^~~~~~
prog.cpp: In member function ‘void GeneralMatching<MAXN>::augment(int, int)’:
prog.cpp:25:18: error: ‘parent’ was not declared in this scope
       parent_v = parent[v];
                  ^~~~~~
prog.cpp:26:16: error: ‘match’ was not declared in this scope
       next_v = match[parent_v];
                ^~~~~
prog.cpp: In member function ‘int GeneralMatching<MAXN>::lca(int, int)’:
prog.cpp:36:18: error: ‘aux’ was not declared in this scope
     while (!v || aux[v] != label) {
                  ^~~
prog.cpp:39:13: error: ‘origin’ was not declared in this scope
         v = origin[parent[match[v]]];
             ^~~~~~
prog.cpp:39:20: error: ‘parent’ was not declared in this scope
         v = origin[parent[match[v]]];
                    ^~~~~~
prog.cpp:39:27: error: ‘match’ was not declared in this scope
         v = origin[parent[match[v]]];
                           ^~~~~
prog.cpp:41:7: error: ‘swap’ was not declared in this scope
       swap<int>(u, v);
       ^~~~
prog.cpp:41:12: error: expected primary-expression before ‘int’
       swap<int>(u, v);
            ^~~
prog.cpp: In member function ‘void GeneralMatching<MAXN>::blossom(int, int, int)’:
prog.cpp:47:12: error: ‘origin’ was not declared in this scope
     while (origin[v] != a) {
            ^~~~~~
prog.cpp:48:7: error: ‘parent’ was not declared in this scope
       parent[v] = w;
       ^~~~~~
prog.cpp:49:11: error: ‘match’ was not declared in this scope
       w = match[v];
           ^~~~~
prog.cpp:50:11: error: ‘visited’ was not declared in this scope
       if (visited[w] == 1) {
           ^~~~~~~
prog.cpp:51:9: error: ‘que’ was not declared in this scope
         que.push(w);
         ^~~
prog.cpp: In member function ‘bool GeneralMatching<MAXN>::bfs(int)’:
prog.cpp:60:10: error: ‘visited’ was not declared in this scope
     fill(visited.begin() + 1, visited.begin() + 1 + N, -1);
          ^~~~~~~
prog.cpp:60:58: error: there are no arguments to ‘fill’ that depend on a template parameter, so a declaration of ‘fill’ must be available [-fpermissive]
     fill(visited.begin() + 1, visited.begin() + 1 + N, -1);
                                                          ^
prog.cpp:60:58: note: (if you use ‘-fpermissive’, G++ will accept your code, but allowing the use of an undeclared name is deprecated)
prog.cpp:61:10: error: ‘origin’ was not declared in this scope
     iota(origin.begin() + 1, origin.begin() + 1 + N, 1);
          ^~~~~~
prog.cpp:61:55: error: there are no arguments to ‘iota’ that depend on a template parameter, so a declaration of ‘iota’ must be available [-fpermissive]
     iota(origin.begin() + 1, origin.begin() + 1 + N, 1);
                                                       ^
prog.cpp:62:5: error: ‘que’ was not declared in this scope
     que = queue<int>();
     ^~~
prog.cpp:62:11: error: ‘queue’ was not declared in this scope
     que = queue<int>();
           ^~~~~
prog.cpp:62:17: error: expected primary-expression before ‘int’
     que = queue<int>();
                 ^~~
prog.cpp:62:17: error: expected ‘;’ before ‘int’
prog.cpp:68:20: error: ‘graph’ was not declared in this scope
       for (int x : graph[v]) {
                    ^~~~~
prog.cpp:70:11: error: ‘parent’ was not declared in this scope
           parent[x] = v;
           ^~~~~~
prog.cpp:72:16: error: ‘match’ was not declared in this scope
           if (!match[x]) {
                ^~~~~
prog.cpp:76:20: error: ‘match’ was not declared in this scope
           que.push(match[x]);
                    ^~~~~
prog.cpp: In member function ‘int GeneralMatching<MAXN>::Match()’:
prog.cpp:91:5: error: ‘vector’ was not declared in this scope
     vector<int> V(N - 1);
     ^~~~~~
prog.cpp:91:12: error: expected primary-expression before ‘int’
     vector<int> V(N - 1);
            ^~~
prog.cpp:92:10: error: ‘V’ was not declared in this scope
     iota(V.begin(), V.end(), 1);
          ^
prog.cpp:92:31: error: there are no arguments to ‘iota’ that depend on a template parameter, so a declaration of ‘iota’ must be available [-fpermissive]
     iota(V.begin(), V.end(), 1);
                               ^
prog.cpp:93:48: error: there are no arguments to ‘mt19937’ that depend on a template parameter, so a declaration of ‘mt19937’ must be available [-fpermissive]
     shuffle(V.begin(), V.end(), mt19937(0x94949));
                                                ^
prog.cpp:94:19: error: range-based ‘for’ expression of type ‘auto’ has incomplete type
     for (auto x : V)
                   ^
prog.cpp:95:12: error: ‘match’ was not declared in this scope
       if (!match[x]) {
            ^~~~~
prog.cpp:96:23: error: ‘graph’ was not declared in this scope
         for (auto y : graph[x]) {
                       ^~~~~
prog.cpp:106:12: error: ‘match’ was not declared in this scope
       if (!match[i] && bfs(i)) ++ans;
            ^~~~~

Standard output is empty