그래프를 확인하는 방법은 2 색 가능합니까?

Question

그래프가 2 색 가능 또는 그 이상인지를 찾고 싶습니다. bipartite 또는 non-bipartite.

여기 내 코드는 C++입니다. Welsh Powell Algorithm을 사용하고 있는데 코드에서 잘못된 부분이있을 수 있습니다. 일부 구석이나 일부 실수가 누락되었을 수 있습니다.

입력 n = 아니오. 정점의 m = no. 에지 기반, 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

그래프가 bipartite임을 보여주기 위해 멋진 알고리즘을 확인할 필요가 없습니다. 착색 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 린은 이러한 도움에 감사드립니다을 다음과 같이 구현 될 수있다.

글쎄, 당신의 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; 
}