2部グラフC++

Question

特定の隣接行列で表されるグラフが2部グラフであるかどうかをチェックする必要があります。いくつかのコードを書きましたが、以下のテスト隣接行列に対しては常にfalseが返されます。trueを返す必要があります。

入力：

10 

0 1 0 0 1 0 0 0 0 0 

1 0 0 0 0 0 0 0 0 0 

0 0 0 1 0 0 1 1 0 1 

0 0 1 0 0 1 0 0 1 0 

1 0 0 0 0 0 0 0 0 0 

0 0 0 1 0 0 0 1 0 1 

0 0 1 0 0 0 0 0 1 0 

0 0 1 0 0 1 0 0 1 0 

0 0 0 1 0 0 1 1 0 0 

0 0 1 0 0 1 0 0 0 0 

出力：

YES 
1 3 6 9 

コード：

#include <iostream> 
#include <fstream> 
#include <vector> 
#include <queue> 

using namespace std; 

bool bipartite=true; 
vector<vector<int>>g; 
vector<int>visit; 
vector<int>colour; 
int n; 

void dfs(int v) 
{ 
    visit[v] = 1; 
    if (colour[v] == 0) 
    { 
     colour[v] = 1; 
    } 
    for (int i = 0; i < g[v].size(); i++) 
    { 
     if (visit[i] == 0) 
     { 
      if (colour[v] == 1) 
      { 
       colour[i] = 2; 
      } 
      else 
       colour[i] = 1; 
      dfs(i); 
     }  
     if (visit[i] == 1 && colour[i] == colour[v]) 
      bipartite = false; 
    } 

} 

int main() 
{ 
    ifstream fin("input.in"); 
    ofstream fout("output.out"); 
    int a; 

    fin >> n; 
    g.resize(n);  
    visit.resize(n); 
    colour.resize(n); 

    for (int i = 0; i < g.size(); i++) 
    {  
     for (int j = 0; j < n; j++) 
     { 
      fin >> a;   
      g[i].push_back(a); 
     } 
    } 

    for (int i = 0; i < n; i++) 
    {  
     if (visit[i] == 0) 
      dfs(i); 
    } 

    cout << bipartite; 

    return 0; 
} 

Answer 1

これはあなたの問題を解決する必要があります。 でも自分のコードとほぼ同じですが、自分のコードが動作する理由を調べてみてください。

ヒント：DFS機能に書いたif (visit[i] == 0)の文を考えてみて

#include <iostream>  
#include <fstream>  
#include <vector>  
#include <queue>  

using namespace std;  

bool bipartite=true;  
vector<vector<int> > g;  
vector<int>visit;  
vector<int>colour;  
int n;  

void dfs(int v, int p)  
{  
    visit[v] = 1;  
    colour[v] = p;  

    for (int i = 0; i < g[v].size(); i++)  
    {  
     if(g[v][i]) {  
      if (visit[i] == 0) {  
       dfs(i, 1-p);  
      } else {  
       if(colour[i] == colour[v]) 
        bipartite = false; 
      }  
     }  
    }  
}  


int main()  
{  
    ifstream fin("input.in");  
    ofstream fout("output.out");  
    int a;  

    fin >> n;  
    g.resize(n);   
    visit.resize(n);  
    colour.resize(n);  

    for (int i = 0; i < g.size(); i++)  
    {   
     for (int j = 0; j < n; j++)  
     {  
      fin >> a;    
      g[i].push_back(a);  
     }  
    }  

    for (int i = 0; i < n; i++)  
    {   
     if (visit[i] == 0)  
      dfs(i, 0);  
    }  

    for(int i=0; i<n; ++i) { 
     if(colour[i] == 1) cout << i << " "; 
    } 
    cout << endl;  

    for(int i=0; i<n; ++i) { 
     if(colour[i] == 0) cout << i << " "; 
    } 
    cout << endl;  

    cout << "Is bipartite: " << bipartite << endl;  

    return 0;  
}