二分图

二分图<==>当且仅当图中不含有奇数环
二分图也可以理解为图中任意一条边的两个端点的颜色不同
证明:
a:充分性:图没矛盾->图中不含奇数环,if有奇数环会出现一条边
左右两个端点颜色相同,就矛盾了
b:必要性,图中不含奇数环->二分图,图不会有矛盾,是二分图

bool dfs(int u,int c)
{
      color[u]=c;//涂色
      for(int i=h[u];i!=-1;i=ne[i])
      {
          int j=e[i]；
          if(!color[j])//未染
          {
              if(!dfs(u,3-c)) return false;
          }
          else if(color[j]==c)  return false;//已染判断是否有冲突
      }
      return true;
}

二分图最大匹配<==>左边和右边成功匹配的边的数量的做大值
思想是:当枚举到左边的某一个点u的时候,判断它连接的右边的点j
考虑j是否已经被之前的人匹配了
a:j没被匹配 那就直接true;
b:j被匹配 那判断之前匹配j的点是否可以换个点匹配,可以也是直接true
到最后u都没有匹配到点就直接false;

bool find(int u)
{
    //memset(st,0,sizeof st);这里杀了我
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!st[j])//之前没有考虑过
        {
            st[j]=true;
            if(!match[j]||find(match[j])) //情况a和情况b
            {
                match[j]=u;
                return true;
            }
        }
    }
    return false;
}

st数组

最短路的三个算法和最小生成树的prim都有st数组,但含义不是都一致
a:dijkstra的st数组表示某个点i是否在集合里,这个集合是已经确定的到i的最短距离dist[i],所以更新之前
要判断st

b:堆优化dijkstra也是同样的道理,所以得到b=t.second的时候要判断是否已经st[b]=true;

c:spfa的st数组表示i这个点是否在队列中,所以插入i之前要判断i是否已经在队列里了

d:prim算法的st数组表示说i这个点是否在集合里,这个集合是已经连完成的”最小生成森林”,
也可以说是生成的最小生成树中连接这个点i的边最小