Как проверить, является ли график 2-раскрашенным или нет?
Я хочу выяснить, является ли график 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;
}
Решение
Чтобы показать, что график является двудольным, вам не нужен причудливый алгоритм для проверки. Вы можете просто использовать функцию раскраски 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
}
}
}
Другие решения
Оригинальная проблема: https://www.codechef.com/problems/CHFNFRN
@ Бенсон Лин Спасибо за такую помощь.
Что ж, проблема с вашим ответом состоит в том, что он потерпит неудачу, если граф отключен, т.е. если у него есть 2 отключенных подграфа.
Так как мы выбираем исходный узел случайным образом, вышеприведенный код просто проверяет для этого подграфа с этим узлом и дает ответ только для подграфа, а не для графа.
С небольшими изменениями в приведенном выше коде мы можем решить эту проблему.
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;
}