7-Laboratoriya jumısı. Tema : Shuqırlıq boyınsha izlew algoritmı (dfs)

#include
#include


using namespace std;


const int max_n = 100005; // Berilishi mumkin bo'lgan maksimal uchlar soni
bool used[max_n]; // Ko'rilgan yoki ko'rilmaganligini bildiruvchi mantiqiy qiymat.
vector<int> g[max_n];
int color[max_n]; // Uchlarni rangi, dastlab barchasi 0 ga teng va u bu uchga hali tashrif buyirilmaganligini bildiradi, agar 1 ga teng bo'lsa bu uch ko'rilgan lekin hali aktiv ya'ni undan chiqib ketilmagan. 2 bo'lsa bu uchdan orqaga chiqib ketgan
int tin[max_n], tout[max_n];
int timer = 0; // Bu uchga nechanchi marta tashrif butirilganligini bildiruvchi sanagich


void dfs(int v) { // Chuqurlik bo'yicha izlash funksiyasi
used[v] = 1; // Hozirgi uchga tashrif buyirildi deb belgilab qo'yamiz;
color[v] = 1;//Bu uchga birinchi marta kirishda uning rangini 1 bilan belgilaymiz;
tin[v] = timer++; // Kirish vaqtini belgilab ketamiz
for (int i = 0; i < (int)g[v].size(); i++) { // v uchning qo'shnilarini ko'rib chiqamiz
int to = g[v][i]; // v uchning navbatdagi qo'shnisi
if (!used[to]) { // Bu qo'shni uch hali ko'rilmagan bo'lsa
dfs(to);
}
}
color[v] = 2;
tout[v] = timer++; // Undan chiqishda uni 2-ranga bo'yab
}


int main() {
int n, m;
cin>>n>>m; // Uchlar soni va bog'lanishlar soni
int v1, v2;
for (int i = 1; i <= m; i++) {
cin>>v1>>v2;
g[v1].push_back(v2); //v2 uchni v1 uchning qo'shnilari ro'yxatiga qo'shamiz. Agar graf orientrlanmagan bo'lsa u holda g[v2].push_back(v1) ni ham yozamiz
}
for (int i = 1; i <= n; i++) {
if (!used[i]) {
dfs(i); // Agar ko'rilmagan uch bo'lsa bu uch orqali navbatdagi chuqurlik bo'yicha izlashni davom ettiramiz.
}
}
return 0;
}

Bu yerdagi color massivi uchlarning rangi. tin massiv bu uchga birinchi marta kirish vaqti, tout bu uchdan chiqib ketish vaqti.

Qo’llasnilishi.

1. 
   Grafning komponentalarni aniqlash. Buning uchun navbatdagi hali ko’rilmagan uch orqali dfs funksiyasiga yuboramiz. Bu o’tib chiqishda u unga bog’langan barcha uch orqali o’tib chiqadi, va ular bitta graf komponentasi deb aytiladi. Komponentalar soni dfs funksiyasiga necha marta murojaat qilganimiz soni.
   
2. 
   Leksikografik tartibdagi birinchi yo’lni aniqlash. Qirralar uzunliklari boyicha leksikografik jahatdan bir uchdan ikkinch uchga boradigan eng kichik yo’lni topish kerak. Buning uchun har bir uchning qo’shnilarini istalgan tartibda emas, balki ularning nomerlari o’sish tartibida ko’rib chiqamiz.
   
3. 
   Grafni ikki ranga bo’yash. Orientrlanmagan grafni ikki hil ranga bo’yash kerak. Bunda agar ikki uch qo’shni bo’ladigan bo’lsa, ularning ranglari har xil bo’lishi kerak. Komponentani boshlab bergan dastlabki uchni 1-ranga bo’yaymiz. Harbir navbatdagi uchga kelganda, uning qo’shnisini ko’rayotganimizda qo’shnisini agar hali ko’rilmagan joriy uch rangiga qarama-qarshi ranga bo’yaymiz, agar allaqachon ko’rilgan bo’lsa u holda u qandaydir ranga bo’yalgan bo’ladi. Masalaning sharti bo’yicha ikkita bog’langan uch har xil ranga ega bo’lishi kerak. Shuning bu ikki uchning ranglarini har xillikga tekshiramiz. Agar ular bir xil bo’lsa u holda berilgan grafni ikkita ranga bo’yab bo’lmaydi.