Алгоритм програмчлал.

Disjoint Set Union (Union Find)-н тухай.  Бидэнд анх аль ч хоёр орой нь хоорондоо холбогдоогүй граф байгаа гэж үзье. Өөрөөр хэлбэл нийт N ширхэг компонент байгаа. Нийт Q ширхэг холболт байгаа ба x, y гэсэн хоёр оройг холбох ба энэ бүх холболтын дараа нийт хэдэн ширхэг компонент байгааг олох жишээ бодлого бодоцгооё. par[N], s[N] гэсэн array авж үзье. par[x] нь x оройн эцгийг, s[x] нь энэ оройд хэдэн хүү байгааг хадгална. Анх бүх i-н хувьд par[i] = i, s[i] = 1 байна. Эхлээд find(x) гэсэн функц тодорхойлъё. Энэ нь x гэсэн оройн хамгийн дээд эцэг буюу root оройг буцаана. par[r] == r тохиолдолд энэхүү r орой нь root. Учир нь r оройн эцэг нь өөрөө тул үүнээс дээш орой үгүй. Одоо буцаад x, y хоёр оройг холбох асуудалдаа орцгооё. Холбохын тулд эхлээд бид rootX = find(x), rootY = find(y) гэж олбол x, y гэсэн хоёр оройн тус тусын хамгийн дээд эцгийг олж чадсан гэсэн үг. Хэрвээ энэ хоёр орой нь ижилхэн бол x, y хоёр орой нь аль хэдийн нэг компонентэд байгаа нь тодорхой. Энэ тохиолдолд бид ...

Backtrack-н тухай. Бидэнд нэг граф өгөгдсөн гэж үзье. Мөн X, Y гэсэн хоёр тоо өгөгдөх ба энэ нь X оройгоос Y орой хүрэх бүх боломжит замыг хэвлэ гэсэн бодлого байг. Энэ замд нэг орой нэг л удаа орно. Энэхүү бодлогыг DFS ашиглан бодоцгооё. Эхлээд vis[U] = 1 байвал U гэсэн орой нь одоо явж байгаа замд орсон гэж үзье. Эсрэг тохиолдолд ороогүй. Хэрхэн бид замаа хадгалах вэ? S[] гэсэн массивын эхний  элемент  гэдэг нь одоо явж байгаа замын эхний орой,  дараагийн   элемент  нь дараагийн орой гэх мэт хадгална. Тэгвэл энэ замд хэдэн орой орсныг хадгалах cnt гэсэн тоог  авъя . Эхлээд cnt = 0, vis- ын  бүх утга 0 байна. X оройгоос гүний нэвтрэлтээ хийж эхэлье. dfs нь одоо U орой дээр явж байгаа гэж үзье. Хэрвээ энэ орой нь Y оройтой ижил бол бид нэг зам олж чадсан гэсэн үг ба S[1], S[2], ..., S[cnt] хүртэлх бүх оройг хэвлэх ба энэ нь бидний зам. Нэмээд Y оройг хэвлэнэ. Учир нь энэ замд U оройгоо бид нэмээгүй байгаа. Эсрэг тохиолдолд S[cnt+1]=U, vis[U] = 1 болн...

DFS-н тухай Энэ удаад DFS буюу гүний нэвтрэлт гэх алгоритмын тухай бичих болно. Жишээ нь бидэнд нэг граф өгөгдсөн ба энэ графт хэдэн компонент буюу хэдэн салангид хэсэг байгааг ол гэсэн бодлого байг. Бид 1-р оройгоос энэ оройтой холбогдсон эхний орой луу очъё. Дараа нь тэр оройтой холбогдсон гэхдээ 1-р оройгоос ялгаатай эхний орой луу очъё. Хэрвээ 1-р орой дээр очих юм бол хязгааргүй үргэлжилнэ . Дараа нь тэр оройгоос түүнтэй холбогдсон гэхдээ өмнө нь очоогүй   орой луу  очно. Энэ мэт бид нэг орой дээр иртэл үүнтэй холбогдсон бүх орой дээр өмнө нь ямар нэгэн байдлаар ирсэн бол яах вэ? Энэ тохиолдолд бид энэ орой дээр ирсэн орой луу буцна гэсэн үг юм. Тэгээд тэр оройн 2дахь өмнө очоогүй   орой л уу   явна. Гэх мэт цааш яваад гацлаа. Тэгвэл дахиад буцна. Гэх мэт үргэлжилсээр 1-р оройтой ямар нэгэн байдлаар   холбогдсон   орой дээр   очсон байх болно. Тэгвэл энэ нь 1 компонент болох юм. Хэрвээ 2-р орой энэ   компонентод   орж чадаагүй бол...