二分图

• [好的网页] 基本二分图*1 基本二分图*2 KM算法

• [定义~]

  二分图又称作二部图，是图论中的一种特殊模型。 设是一个无向图，如果顶点V可分割为两个互不相交的子集，并且图中的每条边所关联的两个顶点i和j分别属于这两个不同的顶点集 ，则称图G为一个二分图。

  

  说人话就是这个图可以分成男女两部分，男男不接受，女女不接受，只有男女连边才是二分图

• [判定~]

  二分图嘛，左边的连点一定都是右边嘛，给左边的点染成色，右边点染成色，就可以判断了，我从起点开始，遍历每个点，如果相邻的点是和当前的点是相同的，这就不是二分图~

  int color[];
  bool ok;
  void Get_color(int pos,int co){
      if(ok) return false;
      color[pos]=co;
      for(int i=Head[pos];i;i=Edge[i].Next){
          int v=Edge[i].To;
          if(color[v]==0) Get_color(v,co^1);
          else if(color[v]==co){
              ok=1;
              return ;
          }
      }
  }
  bool pan(){
      for(int i=1;i<=n;i++){
          if(color[i]==0) Get_color(i);
          if(ok) return false;
      }
      return true;
  }