Provera da li je graf bipartitan

Studente i njihova poznanstva možemo predstaviti neusmerenim grafom. Postavlja se pitanje da li je taj graf bipartitan tj. da li mu se čvorovi mogu podeliti u dve grupe tako da sve grane spajaju čvorove iz dve različite grupe.

Ako neki čvor pripada levoj polovini, tada svi njegovi susedi pripadaju desnoj polovini, njihovi susedi levoj polovini, njihovi susedi desnoj i tako dalje. Zato se zadatak može rešiti obilaskom grafa (na primer u dubinu) obeležavajući čvorove naizmenično (za svaki neposećeni čvor se obeležava da li pripada levoj ili desnoj polovini). Ako se prilikom obilaska naiđe na čvor čiji je sused već obeležen tako da pripada istoj polovini kao tekući, tada graf nije bipartitan. Ako se na takav čvor ne naiđe, tada graf jeste bipartitan.

Po uslovima zadatka svi studenti se poznaju posredno, što znači da je graf povezan. Ako graf ne bi bio povezan, postupak pretrage u dubinu i označavanja čvorova bi trebalo ponoviti za svaku komponentu povezanosti zasebno.

bool moze = true;
// svakom cvoru dodeljujemo jednu od dve boje (tj. oznake grupa)
vector<int> boje(n, -1);
int boja = 0;
stack<int> stek;
stek.push(0);
// prvi cvor bojimo prvom bojom
boje[0] = 0;
while (!stek.empty() && moze) {
  int x = stek.top(); stek.pop();
  // susedi trenutnog cvora x treba da budu obojeni suprotnom bojom od x
  boja = 1 - boje[x];
  for (int sused : susedi[x]) {
    // sused je vec obojen pogresnom bojom, pa graf nije bipartitan
    if (boje[sused] != -1 && boje[sused] != boja) {
      moze = false;
      break;
    }
    // sused nije obojen, pa ga bojimo suprotnom bojom od tekuceg cvora x
    if (boje[sused] == -1) {
      boje[sused] = boja;
      stek.push(sused);
    }
  }
}

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> susedi(n);
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    susedi[a].push_back(b);
    susedi[b].push_back(a);
  }

  bool moze = true;
  // svakom cvoru dodeljujemo jednu od dve boje (tj. oznake grupa)
  vector<int> boje(n, -1);
  int boja = 0;
  stack<int> stek;
  stek.push(0);
  // prvi cvor bojimo prvom bojom
  boje[0] = 0;
  while (!stek.empty() && moze) {
    int x = stek.top(); stek.pop();
    // susedi trenutnog cvora x treba da budu obojeni suprotnom bojom od x
    boja = 1 - boje[x];
    for (int sused : susedi[x]) {
      // sused je vec obojen pogresnom bojom, pa graf nije bipartitan
      if (boje[sused] != -1 && boje[sused] != boja) {
        moze = false;
        break;
      }
      // sused nije obojen, pa ga bojimo suprotnom bojom od tekuceg cvora x
      if (boje[sused] == -1) {
        boje[sused] = boja;
        stek.push(sused);
      }
    }
  }

  if (moze) {
    for (int i = 0; i < n; i++)
      if (boje[i] == 0)
        cout << i << " ";
    cout << endl;
  } else
    cout << "-" << endl;
           
  
  return 0;
}

Provera da li je graf bipartitan - Rešenje