f(n, k)-гаар k урвуу хостой n сэлгэмэлийн тоог тэмдэглэе.
1-ээр эхэлсэн сэлгэмэлийн k урвуу хостой сэлгэмэлийн тоо f(n-1, k). Яагаад?
Харин 1 гэсэн тоо сэлгэмэлийн эхнээсээ 2 дахь байрлалд орвол f(n-1, k-1) байна. Яагаад гэхээр 2 дахь байрлалд орох болгондоо хос үүсгэнэ гэсэн үг.
За үүнтэй ижил 1 гэсэн тоо 3, 4.. гээд байрлаад явбал бодлогын хариу яаж нэмэгдэх вэ гэдэгийг хараарай. Тэгэхээр ерөнхий тохиолдолд:
f(n, k) = sum(f(n-1, k-i)) for (0<=i<n) болно.
Дээрх томъёогоор бодвол бодолт O(N^2 * K) болно. Хугацааны хязгаарлалт хэтрэх нь ойлгомжтой.
Томъёогоо эмхэтгээд үзвэл f(n, k) = f(n, k-1) + f(n-1, k) - f(n-1, k-1) болж бодолт O(N*K). Санах ойгоо хэмнэх үүднээс заавал n*k*sizeof(int) авч явах хэрэг байна уу? f(n-1, k), f(n, k)-г хадгалаад явчихаж бас болно.
Энэ бодлого бол Articulation Point-той холбоотой бодлого.
За би уг нь Таржаны алгоритмыг энэ пост дээрээ тайлбарлая гэж бодож энэ удаагийн тэмцээний анализыг 2 хэсэгтэй болгосон юм. Даанч ажил ерөөсөө болж өгөхгүй завгүй байгаа тул таржаны алгоритм тайлбарлахыг дараа болоё. Бодолтруугаа шууд ороё, уг нь их амархан.
Аль нэг оройгоос гүний нэвтрэлт хийгээд гүний нэвтрэлтийн модоо үүсгэе
1 дугаартай хүсэлтийн хувьд:
a, b, c, d гэж үзье. Мөн гүний нэвтрэлтийн модны хувьд d орой нь c оройн доор байрлаж байгаа гэж үзье. Үнэндээ бидэнд d орой хамгийн чухал. d орой articulation point биш буюу ямар нэгэн циклд агуулагдсан бол c-d ирмэгийг устгахад a->b очиж чадах нь ойлгомжтой. d орой харин articulation point бол бид a болон b орой d оройн доор хоюул оршиж байна уу эсвэл дээр хоюул оршиж байна уу гэдэгийг шалгах хэрэгтэй.
2 дугаартайг ч гэсэн графын хаана байрлаж байгаагаас шалтгаалаад тооцоолчихно, кодноос дэлгэрэнгүй хараарай. Асууж тодруулах зүйл байвал коммент үлдээгээрэй, дуртай бас шуурхай хариулах болно оо
