DFS-н тухай
Энэ удаад DFS буюу гүний нэвтрэлт гэх алгоритмын тухай бичих болно. Жишээ нь бидэнд нэг граф өгөгдсөн ба энэ графт хэдэн компонент буюу хэдэн салангид хэсэг байгааг ол гэсэн бодлого байг. Бид 1-р оройгоос энэ оройтой холбогдсон эхний орой луу очъё. Дараа нь тэр оройтой холбогдсон гэхдээ 1-р оройгоос ялгаатай эхний орой луу очъё. Хэрвээ 1-р орой дээр очих юм бол хязгааргүй үргэлжилнэ. Дараа нь тэр оройгоос түүнтэй холбогдсон гэхдээ өмнө нь очоогүй орой луу очно. Энэ мэт бид нэг орой дээр иртэл үүнтэй холбогдсон бүх орой дээр өмнө нь ямар нэгэн байдлаар ирсэн бол яах вэ? Энэ тохиолдолд бид энэ орой дээр ирсэн орой луу буцна гэсэн үг юм. Тэгээд тэр оройн 2дахь өмнө очоогүй орой луу явна. Гэх мэт цааш яваад гацлаа. Тэгвэл дахиад буцна. Гэх мэт үргэлжилсээр 1-р оройтой ямар нэгэн байдлаар холбогдсон орой дээр очсон байх болно. Тэгвэл энэ нь 1 компонент болох юм. Хэрвээ 2-р орой энэ компонентод орж чадаагүй бол энэ нь тусдаа нэг компонент байгаа бөгөөд энэ оройгоос dfs бичих юм. Хэрвээ үгүй бол энэ нь 1-р оройтой ямар нэгэн байдлаар холбогдсон ба эхний компонентод орсон гэсэн үг. Гэх мэт N оройн хувьд явах бөгөөд компонентын тоо гэдэг бол dfs хэдэн удаа хийсэн бэ? гэсэн үг болно. Доорх зурган дээр илүү ойлгомжтой байгаа. Мөн доорх код энэ хаяг дээр байгаа.
Энэ удаад DFS буюу гүний нэвтрэлт гэх алгоритмын тухай бичих болно. Жишээ нь бидэнд нэг граф өгөгдсөн ба энэ графт хэдэн компонент буюу хэдэн салангид хэсэг байгааг ол гэсэн бодлого байг. Бид 1-р оройгоос энэ оройтой холбогдсон эхний орой луу очъё. Дараа нь тэр оройтой холбогдсон гэхдээ 1-р оройгоос ялгаатай эхний орой луу очъё. Хэрвээ 1-р орой дээр очих юм бол хязгааргүй үргэлжилнэ. Дараа нь тэр оройгоос түүнтэй холбогдсон гэхдээ өмнө нь очоогүй орой луу очно. Энэ мэт бид нэг орой дээр иртэл үүнтэй холбогдсон бүх орой дээр өмнө нь ямар нэгэн байдлаар ирсэн бол яах вэ? Энэ тохиолдолд бид энэ орой дээр ирсэн орой луу буцна гэсэн үг юм. Тэгээд тэр оройн 2дахь өмнө очоогүй орой луу явна. Гэх мэт цааш яваад гацлаа. Тэгвэл дахиад буцна. Гэх мэт үргэлжилсээр 1-р оройтой ямар нэгэн байдлаар холбогдсон орой дээр очсон байх болно. Тэгвэл энэ нь 1 компонент болох юм. Хэрвээ 2-р орой энэ компонентод орж чадаагүй бол энэ нь тусдаа нэг компонент байгаа бөгөөд энэ оройгоос dfs бичих юм. Хэрвээ үгүй бол энэ нь 1-р оройтой ямар нэгэн байдлаар холбогдсон ба эхний компонентод орсон гэсэн үг. Гэх мэт N оройн хувьд явах бөгөөд компонентын тоо гэдэг бол dfs хэдэн удаа хийсэн бэ? гэсэн үг болно. Доорх зурган дээр илүү ойлгомжтой байгаа. Мөн доорх код энэ хаяг дээр байгаа.
- #include <vector>
- #include <iostream>
- using namespace std;
- int n, m; // орой болон ирмэгийн тоо
- int comp; // бидний хариу буюу компонентийн тоо
- bool vis[200000]; // ирсэн ирээгүйг хадгалах массив
- vector<int> adj[200000]; // графын мэдээллийг хадгалах вектор
- void dfs(int u) {
- // одоо бид u гэсэн орой дээр ирж байгаа тул
- vis[u] = 1; // ирсэн гэж тэмдэглэнэ
- for(int v:adj[u]) {
- // v:adj[u] гэдэг нь v гэсэн тоо нь adj[u] гэсэн векторт байгаа
- // бүх элемэнтийн утгыг авна гэсэн үг ба эхнээс нь дуустал явна
- if( !vis[v] ) {
- // v гэсэн орой дээр өмнө нь ямар нэгэн байдлаар очоогүй бол
- // энэ оройгоос цааш явах ёстой гэсэн үг
- dfs(v);
- }
- }
- }
- int main() {
- cin >> n >> m;
- while( m-- ) {
- int u, v; // u, v 2 орой хоорондоо шууд ирмэгээр
- // холбогддог гэсэн үг
- cin >> u >> v;
- adj[u].push_back( v );
- adj[v].push_back( u );
- }
- for(int i = 1; i <= n; i++) {
- if( !vis[i] ) {
- // Энэ нь I-р орой дээр өмнө ямар нэгэн байдлаар очиж чадаагүй
- // гэсэн үг тул энэ оройг агуулсан нэг компонент байх нь
- // тодохрой тул компонентын тоо нь 1-р нэмэгдэнэ
- comp++;
- dfs( i ); // энэ оройтой ямар нэгэн байдлаар холбогдсон бүх
- // орой нь энэ компонетэд орно.
- }
- }
- cout << comp << endl; // хариуг хэвлэнэ.
- return 0;
- }
Comments
Post a Comment