二分图的判定

核心思路

    if (!color[v]) {
      if (!dfs(v, 3 - c)) return false;
    }
    else if (color[v] == color[u]) return false;

完整代码

#include <iostream>
#include <vector>
using namespace std;
const int maxn = 1e6 + 10;
int n, m, color[maxn];
vector<int> g[maxn];

bool dfs(int u, int c) {
  color[u] = c;
  
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i];
    if (!color[v]) {
      if (!dfs(v, 3 - c)) return false;
    }
    else if (color[v] == color[u]) return false;
  }
  
  return true;
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 1; i <= n; i++) {
    if (!color[i] && !dfs(i, 1)) {
      puts("No");
      return 0;
    }
  }
  puts("Yes");  
  return 0;
}

 

 

二分图的最大匹配（匈牙利算法）

核心思路

    if (!book[v]) {
      book[v] = 1;
      if (!match[v] || find(match[v])) {
        match[v] = u;
        return true;
      } 
    }

book数组：每轮尝试的时候初始化为0

表示在这一论尝试中，n2中的某对象是否被预定

以便先前的n1另寻所爱

 

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = 1e6 + 10;
int n1, n2, m, match[maxn];
int book[maxn];
vector<int> g[maxn];

int find(int u) {
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i];
    if (!book[v]) {
      book[v] = 1;
      if (!match[v] || find(match[v])) {
        match[v] = u;
        return true;
      } 
    }
  }
  return false;
}

int main() {
  cin >> n1 >> n2 >> m;
  while (m--) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
  }
  int ans = 0;
  for (int i = 1; i <= n1; i++) {
    memset(book, 0, sizeof book);
    if (find(i)) ans++;
  }
  cout << ans;
  return 0;
}