Je veux trouver si le graphique est 2-colorable ou pas plus à savoir. bipartite ou non bipartite.Comment vérifier que le graphique est en 2 couleurs ou non?
Voici mon code en C++ J'utilise Welsh Powell Algorithm mais il y a quelque chose qui ne va pas dans le code, peut-être qu'il me manque des cas de coin ou une erreur logique.
Entrée n = non. de sommet, m = non. des arêtes, 0 indexation basée
#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;
}
S'il vous plaît expliquer comment vous savez que c'est faux? – Guenther
c'est d'un concours en direct donc je ne peux pas discuter de la question ici. –
Comment voulez-vous que nous vous aidions si vous ne pouviez pas en discuter? – SurvivalMachine