Eyler sayri - cho‘qqilarga tashrif buyurish tartibi
Qirralarni qirrasi uchlari bo‘lgan va cho‘qqilarining kirish va chiqish vaqtlariga ko‘ra tasniflash mumkin.
Bunday tasnif ko‘pincha turli masalalarda qo‘llaniladi.
DFS bajariladi va uchragan barcha qirralar quyidagi qoidalarga ko‘ra tasniflanadi:
Agar cho‘qqisi tashrif buyurilmagan bo‘lsa:
Agar cho‘qqisi allaqachon tashrif buyurilgan bo‘lsa:
Orqaga qirralar (Back Edges) — agar ning ajdodi bo‘lsa, u holda qirrasi orqaga qirra hisoblanadi.
cho‘qqisi ning ajdodi bo‘ladi faqat va faqat biz ga allaqachon kirgan bo‘lsak, lekin hali undan chiqmagan bo‘lsak.
Orqaga qirralar siklni yakunlaydi, chunki ajdodidan avlodiga (DFS daraxtida) yo‘l mavjud va avlodidan ajdodiga qirra (orqaga qirra) mavjud. Shunday qilib sikl hosil bo‘ladi.
Sikllar orqaga qirralar yordamida aniqlanishi mumkin.
Oldinga qirralar (Forward Edges) — agar ning avlodi bo‘lsa, u holda qirrasi oldinga qirra hisoblanadi.
Boshqacha aytganda, agar biz ni allaqachon tashrif buyurib undan chiqqan bo‘lsak va bunda bo‘lsa, u holda qirrasi oldinga qirra hisoblanadi.
Kesishuvchi qirralar (Cross Edges) — agar ning na ajdodi, na avlodi bo‘lsa, u holda qirrasi kesishuvchi qirra hisoblanadi.
Boshqacha aytganda, agar biz ni allaqachon tashrif buyurib undan chiqqan bo‘lsak va bunda bo‘lsa, u holda qirrasi kesishuvchi qirra hisoblanadi.
Bu yerda:
Eslatma:
DFS bajarilishida har bir cho‘qqiga ikki vaqt lahzasi mos qo‘yiladi:
Agar DFS vaqtida cho‘qqilarni kirish tartibida ( bo‘yicha) massivga yozib borilsa, muhim xossa paydo bo‘ladi:
cho‘qqining ost-daraxtidagi barcha cho‘qqilar tartibida uzluksiz kesmani hosil qiladi.
cho‘qqi cho‘qqining ost-daraxtida joylashadi faqat va faqat quyidagi holda
Bu DFS-raqamlashning fundamental xossasidir.
DFS shunday tuzilgan:
Shundan kelib chiqadiki:
Shuning uchun ularning qiymatlari intervali ichida yotadi.
cho‘qqi cho‘qqining ajdodi bo‘ladi faqat va faqat quyidagi holda
tin/tout xossasi daraxtdagi masalalarni massivdagi masalalarga keltirish imkonini beradi.
Cho‘qqining ost-daraxti kesmaga aylanadi:
Shuning uchun daraxtlardagi ko‘plab masalalar massivlar uchun tuzilmalar bilan yechiladi:
int tim; // timer
int tin[N]; // time when dfs got in to vertex x
int tout[N]; // time when dfs gout out from vertex x
bool used[N]; // true if vertex x was visited
vector<int> v[N]; // edges
void dfs(int x) {
used[x] = true; // mark current vertex as visited
tin[x] = (++timer); // time when x is visited
for (int y: v[x]) {
if (used[y]) { // already visited vertex
if (tout[y] == 0) { // dfs didn't get out yet from vertex y
// back edge
} else if (tin[x] < tin[y]) {
// forward edge
} else {
// cross edge
}
continue;
}
// (x, y) is tree edge
dfs(y);
}
tout[x] = timer; // time when dfs gets out from vertex x
}