如何檢查圖形是否可着色？

Question

我想查找圖形是否可以2色或不更多。雙方或非雙方。

這裏是我在C++中的代碼我正在使用威爾士鮑威爾算法，但代碼中有些錯誤可能是我錯過了一些角落案例或一些邏輯錯誤。

輸入n =沒有。頂點，m =否。基於0的索引

#include <iostream> 
#include <algorithm> 
using namespace std; 


pair <int,int> s[1001]; 
int comp(pair <int,int> s1, pair <int,int> s2) 
{ 
    if(s1.first>s2.first) 
     return 0; 
    else 
     return 1; 
} 
int main() 
{ 

     int n,i,j,k,flag=0; 
     bool a[1001][1001]={false}; 
     int s1[1001]={0}; 
     int s3[1001]={0}; 
     for(i=0;i<1001;i++) 
     { 
      s[i].first=0; 
      s[i].second=i; 
      //s1[i]=0; 
     } 
     long long m; 
     cin>>n>>m; 
     while(m--) 
     { 
      int x,y; 
      cin>>x>>y; 
      if(x==y) 
       continue; 
      a[x][y]=true; 
      a[y][x]=true; 
     } 

     for(i=0;i<n;i++) 
      for(j=0;j<n;j++) 
      if(a[i][j]==true) 
      s[i].first++; 

     sort(s,s+n,comp); 
     int color=1,p=0,z,f; 

     for(i=0;i<n;i++) 
     { 
      k = s[n-i-1].second; 
      if(s1[k]==0) 
      { 
       s1[k]=color; 
       p=0; 
        s3[p++]=k; 
        for(j=n-1;j>=0;j--) 
        { 
         f=0; 
         if(s1[s[j].second]==0) 
         { 
          for(z=0;z<p;z++) 
          { 
           if(a[s3[z]][s[j].second]==false || s3[z]==s[j].second) 
            continue; 
           else 
           { 
            f=1; 
            break; 
           } 
          } 
          if(f==1) 
           continue; 
          else 
          { 
           s3[z]=s[j].second; 
           p++; 
           s1[s[j].second]=color; 
          } 
         } 
        } 

       color++; 
      } 
      if(color==3) 
       break; 
     } 
     for(i=0;i<n;i++) 
      if(s1[i]==0) 
     { 
      flag=1; 
      break; 
     } 

      if(flag==1) 
      cout<<"NO\n"; 
      else 
      cout<<"YES\n"; 

    return 0; 
} 

Answer 1

要顯示一個圖形是雙向的，您不需要花哨的算法來檢查。您可以簡單地使用着色DFS（深度優先搜索）功能。

int color[100005];    //I assume this is the largest input size, initialise all values to -1. 
vector<int> AdjList[100005]; //Store the neighbours of each vertex 
bool flag = true;    //Bipartite or Not Bipartite 

void dfs(int x, int p){   //Current vertex, Parent Vertex 
    if (!flag) return; 
    if (p == -1) color[x] = 0; 
    else color[x] = 1 - color[p]; 
    for (int i = 0; i < AdjList[x].size(); ++i){  //For Every Neighbour 
     int v = AdjList[x][i];      //Vertex to be checked 
     if (color[v] == color[x]){     //Same color -> Not bipartite 
      flag = false; 
      return; 
     }  
     if (color[v] == -1){       //Unchecked 
      dfs(v,x);         //color 
     }    
    } 
} 

Answer 2

原來的問題：https://www.codechef.com/problems/CHFNFRN

@Benson林謝謝你，這麼幫助它可以實現如下。

那麼你的答案的問題是它失敗了，如果圖表斷開，即如果它有2然後斷開的子圖。 由於我們隨機選擇源節點，因此上面的代碼只是檢查具有該節點的子圖，並且僅針對該子圖給出ans而不是該圖。 通過上面代碼的小改動，我們可以解決這個問題。

int colorArr[1001]; 

bool isBipartite(bool G[][1001], int src,int n) 
{ 
colorArr[src] = 0; 
queue <int> q; 
q.push(src); 
while (!q.empty()) 
{ 
    int u = q.front(); 
    q.pop(); 

    // Find all non-colored adjacent vertices 
    for (int v = 0; v < n; ++v) 
    { 
     // An edge from u to v exists and destination v is not colored 
     if (G[u][v]==true && colorArr[v] == -1) 
     { 
      // Assign alternate color to this adjacent v of u 
      colorArr[v] = 1 - colorArr[u]; 
      q.push(v); 
     } 
     if(G[u][v]==true && colorArr[u]==colorArr[v] && u!=v) 
       return false; 

     // An edge from u to v exists and destination v is colored with 
     // same color as u 
    } 
} 

// call the function with source node which is not color. 
int count=0; 
for(int i=0;i<n;i++) 
{ 

     if(colorArr[i]==-1) 
     { 
      if(isBipartite(G,i,n)) 
      continue; 
      else 
       return false; 
     } 
    for(int j=0;j<n;j++) 
    { 
     if(G[i][j]==true) 
     { 
      if(colorArr[i]==colorArr[j] && colorArr[i]!=-1) 
       return false; 
     } 

    } 
} 

return true; 
}