Как проверить график 2-цветного или нет?

Question

Я хочу найти, является ли граф 2-цветным или не более, т.е. двудольный или недипоральный.

Вот мой код на C++ Я использую алгоритм Уэлша Пауэлла, но что-то не так в коде, возможно, я пропускаю некоторые угловые случаи или какую-то логическую ошибку.

Ввод n = нет. вершины, т = нет. ребра, 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 (Depth-First Search). Он может быть реализован следующим образом:

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 Lin Спасибо за такую ​​помощь.

Ну, проблема с вашим ans - это сбой, если график отключен, если он имеет для 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; 
}