library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub kazunetakahashi/library

:warning: Graph/Bipartite.cpp

Back to top page

Code

#include <vector>
using namespace std;

// ----- Bipartite -----

// for C++14
// Bipartite<> graph(N);

template <typename T = int>
class Bipartite
{
public:
  struct edge
  {
    bool used;
    size_t rev;
    int from, to;
    T id;

    edge(int from, int to, size_t rev, T id = T{}, bool used = false) : used{used}, rev{rev}, from{from}, to{to}, id{id} {}
  };

private:
  int N;
  vector<vector<edge>> G;
  vector<edge *> match;
  vector<bool> used;

public:
  Bipartite(int N) : N{N}, G(N), match(N), used(N) {}

  void add_edge(int u, int v, T id = T{})
  {
    G[u].push_back({u, v, G[v].size(), id, false});
    G[v].push_back({v, u, G[u].size() - 1, id, false});
  }

  int bipartite_matching()
  {
    int res{0};
    fill(match.begin(), match.end(), nullptr);
    for (auto v = 0; v < N; v++)
    {
      if (!match[v])
      {
        fill(used.begin(), used.end(), false);
        if (dfs(v))
        {
          ++res;
        }
      }
    }
    for (auto &e : match)
    {
      if (e)
      {
        e->used = true;
      }
    }
    return res;
  }

  vector<edge *> const &matching() const
  {
    return match;
  }

private:
  bool dfs(int v)
  {
    used[v] = true;
    for (auto &e : G[v])
    {
      if (e.used)
      {
        continue;
      }
      auto u{e.to};
      // for C++14
      auto w{match[u]};
      if (!w || (!used[w->to] && dfs(w->to)))
      {
        match[v] = &e;
        match[u] = &G[u][e.rev];
        return true;
      }
    }
    return false;
  }
};

#line 1 "Graph/Bipartite.cpp"
#include <vector>
using namespace std;

// ----- Bipartite -----

// for C++14
// Bipartite<> graph(N);

template <typename T = int>
class Bipartite
{
public:
  struct edge
  {
    bool used;
    size_t rev;
    int from, to;
    T id;

    edge(int from, int to, size_t rev, T id = T{}, bool used = false) : used{used}, rev{rev}, from{from}, to{to}, id{id} {}
  };

private:
  int N;
  vector<vector<edge>> G;
  vector<edge *> match;
  vector<bool> used;

public:
  Bipartite(int N) : N{N}, G(N), match(N), used(N) {}

  void add_edge(int u, int v, T id = T{})
  {
    G[u].push_back({u, v, G[v].size(), id, false});
    G[v].push_back({v, u, G[u].size() - 1, id, false});
  }

  int bipartite_matching()
  {
    int res{0};
    fill(match.begin(), match.end(), nullptr);
    for (auto v = 0; v < N; v++)
    {
      if (!match[v])
      {
        fill(used.begin(), used.end(), false);
        if (dfs(v))
        {
          ++res;
        }
      }
    }
    for (auto &e : match)
    {
      if (e)
      {
        e->used = true;
      }
    }
    return res;
  }

  vector<edge *> const &matching() const
  {
    return match;
  }

private:
  bool dfs(int v)
  {
    used[v] = true;
    for (auto &e : G[v])
    {
      if (e.used)
      {
        continue;
      }
      auto u{e.to};
      // for C++14
      auto w{match[u]};
      if (!w || (!used[w->to] && dfs(w->to)))
      {
        match[v] = &e;
        match[u] = &G[u][e.rev];
        return true;
      }
    }
    return false;
  }
};

Back to top page