Grupa studenata se okupila na letnjem kampu. Svako je znao nekoliko drugih studenata. Ispostavilo se da se svaki par studenata poznaje posredno (preko niza zajedničkih poznanika). Potrebno je da se studenti podele u dve grupe, ali pošto svako želi da upozna što više novih kolega, potrebno je da svaku grupu čine međusobno nepoznate osobe (dve osobe koje se već poznaju ne mogu biti u istoj grupi).
Napisati program koji određuje da li je to moguće i ako jeste, koji će sve studenti biti u grupi sa studentom čiji je redni broj 0.
Sa standardnog ulaza se učitava broj studenata \(n\) (1 ≤ \(n\) ≤ 105), broj parova \(m\) studenata koji se od ranije poznaju (0 ≤ \(m\) ≤ \(n\)(\(n\)−1)/2 ), a zatim i niz parova brojeva od 0 do \(n\) − 1 koji predstavljaju njihova poznanstva.
Na standardni izlaz ispisati redne brojeve studenata koji su u grupi sa studentom koji nosi redni broj 0, u rastućem poretku, ili simbol - ako tražene dve grupe nije moguće formirati.
6 6 0 1 1 2 2 3 3 4 4 5 5 0
0 2 4
Ako su u jednoj grupi studentei sa brojevima 0, 2 i 4, u drugoj su studenti sa brojevima 1, 3 i 5 i tada se ni u jednoj grupi ne nalaze studenti koji se međusobno poznaju.
5 5 0 1 1 2 2 3 3 4 4 0
-
Student 0 ne sme da bude u grupi sa studentom 1, koji ne sme da bude u grupi sa studentom 2, što znači da 0 i 2 moraju da budu u istoj grupi. Studenti 2 i 3 ne mogu da budu u istoj grupi, pa su 1 i 3 u istoj grupi. Student 4 ne sme da bude u grupi sa studentom 3, pa on mora biti u grupi sa studentima 0 i 2, međutim, to nije dopušteno, jer se studenti 4 i 0 poznaju.
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.
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> susedi(n);
int u, v;
for(int i = 0; i < m; i++){
cin >> u >> v;
susedi[u].push_back(v);
susedi[v].push_back(u);
}
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[0] == boje[i])
cout << i << " ";
}
else
cout << "-";
cout << endl;
return 0;
}