算法基础之染色法判定二分图

染色法判定二分图

• 核心思想： 二分图 : 当且仅当图中不含有奇数环(环中边的数量为奇数)

  • 染色法 : 从原点开始染色 1 / 2 当冲突时即含有奇数环

  •   #include <cstring>
      #include <iostream>
      #include <algorithm>
      
      using namespace std;
      const int N = 100010 , M = N * 2;  //无向图
      
      int n,m;
      int h[N],e[M],ne[M],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)
      {
          color[u] = c;  //染色
          
          for(int i = h[u];i!=-1;i = ne[i])  //搜图
          {
              int j = e[i];  //j为编号
              if(!color[j])  //j没有染色
              {
                  if(!dfs(j, 3-c))  //j染色相反  搜j的路 
                  {
                      return false;
                  }
              }
              else if(color[j] == c) return false;  //i 和 j染色一样 说明冲突
          }
          return true;
      }
      
      int main()
      {
          cin>>n>>m;
          
          memset(h,-1,sizeof h);
          while(m--)
          {
              int a,b;
              cin>>a>>b;
              add(a,b) , add(b,a);
          }
          
          bool flag = true;  //标记是否含有奇数环
          for(int i=1;i<=n;i++)
          {
              if(!color[i])  //i没有染色
              {
                  if(!dfs(i,1))  //i染成1
                      		   //如果i>1时 没有染色 因为是无向图 说明i和1不联通 所以原点染色1 / 2 都可以
                  {
                      flag = false;  //返回了false 说明有奇数环
                      break;
                  }
              }
          }
          
          if (flag) puts("Yes");
          else puts("No");
      }