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

#include
#include


using namespace std;


const int max_n = 1005; // Berilishi mumkin bo'lgan maksimal uchlar soni
bool used[max_n]; // Ko'rilgan yoki ko'rilmaganligini bildiruvchi mantiqiy qiymat.
int color[max_n];// Bo'laygan uchlar rangi. 0 va 1 qiymatlarni qabul qiladi.
int n;
int a[max_n][max_n];


void dfs(int v, int col) { // Chuqurlik bo'yicha izlash funksiyasi
used[v] = 1; // Hozirgi uchga tashrif buyirildi deb belgilab qo'yamiz;
color[v] = col;// Uni col rangiga bo'yaymiz
for (int i = 1; i <= n; i++) { // v uchning qo'shnilarini ko'rib chiqamiz
if (a[v][i]==1) {
if (!used[i]) { // Bu qo'shni uch hali ko'rilmagan bo'lsa
dfs(i, 1-col);
}
else if (color[v]==color[i]) {
cout<<"Berilgan grafni ikki har xil ranga bo'yab bo'lmaydi";
exit(0);
}
}
}
}


int main() {
cin>>n; // Uchlar soni va bog'lanishlar soni
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin>>a[i][j]; // Bog'lanish matritsasini o'qiymiz. Uning qiymati 1 bo'lsa i va j uchlar o'rtasida bog'lanish bor, 0 bo'lsa bog'lanish yo'q
}
}
for (int i = 1; i <= n; i++) {
if (!used[i]) {
dfs(i, 0); // Agar ko'rilmagan uch bo'lsa bu uchni 0 ga bo'yaymiz va navbatdagi chuqurlik bo'yicha izlashni davom ettiramiz.
}
}
for (int i = 1; i <= n; i++) {
cout<}
return 0;
}

4. 
   Daraxtda ikkita uchni biri-ikkinchisining ajdodi yoki ajdodi emasligini aniqlash.
   

Masalan quyidagicha daraxt berilgan bo’lsin:


Daraxtning ildizi 1-uch. 4-uching to’g’idan-tog’ri avlaolari 7, 8 va 9. Lekin 11-uch 7-uchning tog’ridan-to’g’ri avlodi bo’lganligi uchun, 11-uch ham 4-uchning avlodi; 4-uchning barcha avlodlari: 7, 8, 9, 11, 12, 13, 14;
Barcha uchlar 1-uchning avlodlari. Bizga ikkita uch beriladi. Vazifa biriinchi uch ikkinchi uchning ajdodi yoki avlado ekanligini yoki ular o’rtasida umuman aloqa yo’q ekenligini aniqlash kerak. Masalan berilgan daraxtda 12 va 6 - uchlarning bir-biriga aloqasi yo’q. Bunday tipli savollarga javob berish uchun kirish va chiqish vaqti tushinchalaridan foydalanamiz. Yuqorida berilgan daraxtni kirish va chiqish vaqtlari bilan birga belgilab chiqamiz. Kirish vaqti qizil rang bilan, chiqish vaqti qora rang bilan berilgan:

4-uchni oladigan bo’lsak uning kishish vaqti uning qism daraxtiga tegishli bo’lgan barcha uchlarning kirish vaqtidan kichik, chunki ularga borish uchun avval bu uch orqali o’tish kerak. Va 4-uchning chiqish vaqti barcha avlaodlari chiqish vaqtlaridan katta. Chunki barcha avlodlardan qaytib kelgach bu uchdan chiqib ketadi(orqaga qaytadi).
Buni aniqlaydigan funksiyani isfather(int v1, int v2) funksiyasi deb nomlaymiz. Bu funksiya agar v1 uch v2 uchning ajdodi bo’lsa 1 qaytaradi, v1 uch v2 uchning avlodi bo’lsa bo’lsa -1 qaytaradi, agar ular bir-biriga bog’liq bo’lmasa 0 qaytaradi. Yana bir mantiqiy funksiya ishlatamiz, bu funksiya isupper(int v1, int v2). Bu funksiya agar v1 uch v2 uchning ajdodi bo’lsa, ya’ni undan yuqoriroqda joylashgan bo’lsa true qaytaradi.