Guruh talabasi Karimov Doston 7-laboratoriya ishi. Mavzu: Chuqurlik bo’yicha izlash algoritmi(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.
   

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

bool isupper(int v1, int v2) {

return tin[v1] <= tin[v2] && tout[v1] >= tout[v2];

}

int isfather(int v1, int v2) {

if (isupper(v1, v2))

return 1;

if (isupper(v2, v1))

return -1;

return 0;

}

4-topshiriq

We consider a geographical map with N countries numbered from 1 to N (0 < N < 99). For every country we know the numbers of other countries which are connected with its border. From every country we can reach to any other one, eventually crossing some borders. Write a program which determines whether it is possible to color the map only in two colors — red and blue in such a way that if two countries are connected their colors are different. The color of the first country is red. Your program must output one possible coloring for the other countries, or show, that such coloring is impossible.

Input

On the first line is written the number N. On the following N lines, the i-th line contains the countries to which the i-th country is connected. Every integer on this line is bigger than i, except the last one which is 0 and marks that no more countries are listed for country i. If a line contains 0, that means that the i-th country is not connected to any other country, which number is larger than i.

Output

The output contains exactly one line. If the coloring is possible, this line must contain a list of zeros and ones, without any separators between them. The i-th digit in this sequence is the color of the i-th country. 0 corresponds to red color, and one — to blue color. If a coloring is not possible, output the integer −1.

Sample

input	output
3 2 0 3 0 0	010

#include

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

const int INF = 1000000000;

int n, m;

enum type {

UNUSED = 0,

RED = 1,

BLUE = 2

};

vector used;

vector > G;

bool x = true;

void dfs(int v, type color = RED) {

if (used[v] == UNUSED) {

used[v] = color;

} else if (used[v]!=color) {

x = false;

return;

}

for (int i=0; i

if (used[G[v][i]] == UNUSED) {

dfs(G[v][i], (color == RED ? BLUE : RED));

} else if (used[G[v][i]]==color) {

x = false;

return; }

}

}

int main() {

scanf("%d", &n);

G.assign(n, vector());

used.assign(n, UNUSED);

for (int i=0; i

int x;

scanf("%d", &x);

while (x) {

G[i].push_back(x-1);

G[x-1].push_back(i);

scanf("%d", &x);

}

}

dfs(0);

if (x) {

for (int i=0; iprintf("%d", used[i]-1);

}

} else {

printf("-1");

}

return 0; }