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 \leq n \leq 10^5\)), broj parova \(m\) studenata koji se od ranije poznaju (\(0 \leq m \leq \frac{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>
using namespace std;
class Graph {
private:
int broj_cvorova;
vector<vector<int>> lista_suseda;
vector<int> boje;
public:
Graph(int broj_cvorova) {
this->broj_cvorova = broj_cvorova;
lista_suseda.resize(broj_cvorova);
// na pocetku, nijedan cvor nije obojen
boje.resize(broj_cvorova, -1);
}
void dodaj_granu(int u, int v) {
lista_suseda[u].push_back(v);
lista_suseda[v].push_back(u);
}
bool dfs(int x) {
int boja = 1 - boje[x];
for (int sused : lista_suseda[x]) {
if (boje[sused] != -1 && boje[sused] != boja) {
return false;
}
if (boje[sused] == -1) {
boje[sused] = boja;
if (!dfs(sused)) {
return false;
}
}
}
return true;
}
void odredi_studente_u_grupi() {
boje[0] = 0;
if(dfs(0)){
for(int i = 0; i < broj_cvorova; i++) {
if(boje[0] == boje[i]) {
cout << i << " ";
}
}
}
else {
cout << "-";
}
cout << endl;
}
};
int main() {
int n, m;
cin >> n >> m;
Graph *G = new Graph(n);
int u, v;
for(int i = 0; i < m; i++){
cin >> u >> v;
G->dodaj_granu(u, v);
}
G->odredi_studente_u_grupi();
return 0;
}Ideja je ista kao u glavnom rešenju: graf se obilazi u dubinu i čvorovi se boje naizmenično sa dve boje. Ako se tokom obilaska naiđe na granu čija su oba kraja iste boje, graf nije bipartitan. Razlika je samo u tome što se ovde pretraga u dubinu realizuje nerekurzivno, pomoću eksplicitnog steka.
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class Graph {
private:
int broj_cvorova;
vector<vector<int>> lista_suseda;
vector<int> boje;
public:
Graph(int broj_cvorova) {
this->broj_cvorova = broj_cvorova;
lista_suseda.resize(broj_cvorova);
boje.resize(broj_cvorova, -1);
}
void dodaj_granu(int u, int v) {
lista_suseda[u].push_back(v);
lista_suseda[v].push_back(u);
}
bool dfs() {
bool bipartitan = true;
int boja = 0;
stack<int> stek;
stek.push(0);
boje[0] = 0;
while (!stek.empty() && bipartitan) {
int x = stek.top();
stek.pop();
boja = 1 - boje[x];
for (int sused : lista_suseda[x]) {
if (boje[sused] != -1 && boje[sused] != boja) {
bipartitan = false;
break;
}
if (boje[sused] == -1) {
boje[sused] = boja;
stek.push(sused);
}
}
}
return bipartitan;
}
void odredi_studente_u_grupi() {
if(dfs()){
for(int i = 0; i < broj_cvorova; i++) {
if(boje[0] == boje[i]) {
cout << i << " ";
}
}
}
else {
cout << "-";
}
cout << endl;
}
};
int main() {
int n, m;
cin >> n >> m;
Graph *G = new Graph(n);
int u, v;
for(int i = 0; i < m; i++){
cin >> u >> v;
G->dodaj_granu(u, v);
}
G->odredi_studente_u_grupi();
return 0;
}