染色法判定二分图

通过对一个点的邻接点进行染色，如果染色发生冲突则不是二分图，如果未发生冲突则是二分图。

原题链接： 染色法判定二分图

规定有0,1,2三种颜色，分别代表未染色，颜色1，颜色2

3-c代表对立的另一种颜色例如3-1=2......3-2=1

#include <bits/stdc++.h>
using namespace std;
const int N = (1e5+10) * 2;
int n,m;
int e[N],ne[N],h[N],idx;
int color[N];

void add(int a,int b){
  e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

bool dfs(int u,int c){//把u染成c色
  color[u] = c;
  for(int i = h[u];i!=-1;i=ne[i]){//对这个点的邻接点进行判断
    int j = e[i];
    if(!color[j]){//如果邻接点未染色
      if(!dfs(j,3-c)) return false;//看看能否染成3-c，也就是另一种颜色
    }else if (color[j] && color[j] != 3 - c){//如果染色了，看看是不是3-c（对立色）
      return false;
    }
  }
  return true;
}

int main(){
  memset(h,-1,sizeof h);
  cin >> n >> m;
  for(int i = 1;i <= m;i++){
    int a,b;
    cin >> a >> b;
    add(a,b),add(b,a);
  }

  for(int i = 1;i <= n;i++){//对所有点进行遍历
    if(!color[i]){//如果没有染色，就对他进行处理
      if(!dfs(i,1)){//没有染色的统一染成1，看看能否成功
        cout << "No" << endl;
        return 0;
      }
    }
  }

  cout << "Yes" << endl;
  return 0;
}

二分图的最大匹配

找对象算法

根据二分图的性质来进行解题。

原题链接： 二分图的最大匹配

这道题虽然是二分图，但是只看一边就行了，因为最大的可能不会更多了。

#include <bits/stdc++.h>
using namespace std;
const int N = 510,M = 1e5+10;
int h[N],ne[M],e[M],idx;
int st[N],match[N];
int n1,n2,m;
int res;
void add(int a,int b){
  e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

bool find(int x){
  for(int i = h[x];i != -1;i = ne[i]){//看他的邻接点
    int j = e[i];
    if(!st[j]){//如果邻接点还未占领
      st[j] = 1;
      if(match[j]==0 || find(match[j])){//如果该邻接点还未匹配或者当前匹配该邻接点的点可以换另一个
        match[j] = x;//那么就让现在的点占领该邻接点
        return true;
      }
    }
  }
  return false;
}

int main(){
  memset(h,-1,sizeof h);
  cin >> n1 >> n2 >> m;
  while(m--){
    int a,b;
    cin >> a >> b;
    add(a,b);//注意是看一边，要是存无向图就错了。应该当有向图看
  }

  for(int i = 1;i <= n1;i++){
    memset(st,0,sizeof st);//每次都重置一下st，为了给后来鸠占鹊巢腾位置
    if(find(i)) res++;//如果他能放开，那匹配数++
  }

  cout << res << endl;
}