Algoritmdan nazorat savollariga javoblar Algoritm nima

#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.