Graf bipartit: verificare prin două culori în C++

Un graf neorientat este bipartit dacă putem împărți vârfurile în două grupuri astfel încât fiecare muchie să lege grupuri diferite. Putem numi grupurile culoarea 0 și culoarea 1. Culorile sunt doar etichete, nu valori ale muchiilor.

O muchie impune culori opuse

Un drum cu muchiile 1–2 și 2–3 poate avea culorile 0,1,0. Dacă adăugăm muchia 3–1, triunghiul nu mai permite două culori: vârfurile 1 și 3 ar trebui simultan să fie egale și diferite la culoare.

Citim 1≤n≤100, apoi m muchii distincte între vârfuri diferite, numerotate 1..n. Graful poate avea mai multe componente separate. Afișăm DA dacă este bipartit, altfel NU. Matricea de adiacență a[u][v] este 1 când există muchia; pentru un graf neorientat completăm și a[v][u].

Ce înseamnă BFS în această soluție

BFS, de la Breadth-First Search, este parcurgerea în lățime. Folosim o coadă, din care extragem primul vârf introdus. La descoperirea unui vecin necolorat, îi atribuim culoarea opusă și îl adăugăm la coadă. Valoarea -1 înseamnă „încă necolorat”.

Dacă întâlnim o muchie cu ambele capete de aceeași culoare, cerința a fost încălcată. Dacă o componentă se termină fără conflict, începem din următorul vârf necolorat. Un vârf izolat poate primi oricare culoare.

Ciclul 1-2-3-4-1 admite culorile alternante: 1 și 3 într-o grupă, 2 și 4 în cealaltă. Fiecare muchie unește grupe diferite.Mărește schema ↗

Varianta cu tablou clasic

#include <iostream>
#include <queue>
using namespace std;
int main() {
    int n,m; cin >> n >> m;
    int a[101][101]={},culoare[101];
    for(int i=1;i<=n;++i) culoare[i]=-1;
    for(int i=0;i<m;++i) { int u,v; cin >> u >> v; a[u][v]=a[v][u]=1; }
    bool bun=true;
    for(int s=1;s<=n && bun;++s) if(culoare[s]==-1) {
        queue<int> q; q.push(s); culoare[s]=0;
        while(!q.empty() && bun) {
            int u=q.front(); q.pop();
            for(int v=1;v<=n;++v) if(a[u][v]) {
                if(culoare[v]==-1) { culoare[v]=1-culoare[u]; q.push(v); }
                else if(culoare[v]==culoare[u]) bun=false;
            }
        }
    }
    cout << (bun?"DA\n":"NU\n");
}

Varianta echivalentă cu std::vector

Păstrăm limitele intrării și aceleași rezultate. Tabloul clasic rezervă capacitatea maximă; vectorul construiește numărul de elemente necesare. Indicii folosiți de algoritm rămân aceiași.

#include <vector>

#include <iostream>
#include <queue>
using namespace std;
int main() {
    int n,m; cin >> n >> m;
    vector<vector<int>> a(n+1,vector<int>(n+1)); vector<int> culoare(n+1);
    for(int i=1;i<=n;++i) culoare[i]=-1;
    for(int i=0;i<m;++i) { int u,v; cin >> u >> v; a[u][v]=a[v][u]=1; }
    bool bun=true;
    for(int s=1;s<=n && bun;++s) if(culoare[s]==-1) {
        queue<int> q; q.push(s); culoare[s]=0;
        while(!q.empty() && bun) {
            int u=q.front(); q.pop();
            for(int v=1;v<=n;++v) if(a[u][v]) {
                if(culoare[v]==-1) { culoare[v]=1-culoare[u]; q.push(v); }
                else if(culoare[v]==culoare[u]) bun=false;
            }
        }
    }
    cout << (bun?"DA\n":"NU\n");
}

De ce verificăm toate componentele

Un triunghi aflat într-o componentă care nu conține vârful 1 face întregul graf nebipartit. O singură pornire din 1 ar rata problema. Bucla exterioară acoperă toate vârfurile, fără a relansa parcurgerea din cele deja colorate.

Când o componentă este conexă, alegerea culorii de start fixează culorile de-a lungul drumurilor. Inversarea tuturor culorilor nu poate repara o muchie ale cărei capete sunt egale. De aceea conflictul nu se rezolvă încercând altă culoare numai pentru primul vârf.

Reprezentarea cu matrice scanează n posibili vecini pentru fiecare vârf, deci timpul este O(n²+m), iar memoria O(n²). Nu folosim aici costul O(n+m) al listelor de adiacență. Tabloul clasic rezervă 101×101 celule pentru indexarea de la 1.

Exersează

Un drum de trei vârfuri este bipartit; un triunghi nu este. Un ciclu de patru vârfuri este bipartit. Testează un vârf izolat plus un triunghi separat, ca să verifici bucla pe componente.

Continuă cu reprezentarea grafurilor, parcurgerea în lățime și componentele conexe.

Întrebări frecvente

Ce este un graf bipartit?

Un graf neorientat ale cărui vârfuri pot fi împărțite în două grupuri astfel încât fiecare muchie să lege grupuri diferite. Echivalent, vârfurile pot primi două culori fără vecini de aceeași culoare.

Cum verific bipartiția folosind BFS?

BFS, parcurgerea în lățime, vizitează vecinii cu ajutorul unei cozi. Atribuie fiecărui vecin nevizitat culoarea opusă; o muchie între două vârfuri deja colorate la fel respinge bipartiția.

Ajunge o singură parcurgere dacă graful este neconex?

Nu. Trebuie pornită o parcurgere din fiecare vârf încă necolorat, astfel încât toate componentele să fie verificate. Un ciclu impar într-o componentă izolată poate face întregul graf nebipartit.