如何检查图形是否可着色？

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; 
}