Lý thuyết cơ bản về DFS và BFS

1. DFS (Depth-First Search - Tìm kiếm theo chiều sâu)

• Bản chất: Đi "cắm đầu" đi sâu nhất có thể theo một hướng. Khi gặp ngõ cụt, mới quay ngược lại (backtrack) ngã rẽ gần nhất chưa khám phá để đi tiếp hướng khác.
• Hình ảnh ví dụ: Giống như đi thám hiểm một cái hang sâu, chọn một ngách và đi sâu mãi đến tận cùng rồi mới quay ra thử các ngách phụ khác.
• Cơ chế: Sử dụng Stack (Ngăn xếp) hoặc Đệ quy.
• Ứng dụng: Duyệt cây, tìm kiếm đường đi, kiểm tra chu trình, thành phần liên thông, quay lui.

2. BFS (Breadth-First Search - Tìm kiếm theo chiều rộng)

• Bản chất: Đi "loang" rộng ra từng lớp một. Đứng ở một điểm, khám phá hết hàng xóm gần nhất (khoảng cách 1 bước) rồi mới dịch chuyển sang các điểm xa hơn.
• Hình ảnh ví dụ: Thả viên sỏi xuống mặt hồ, gợn sóng lan rộng đều ra các phía theo hình tròn đồng tâm.
• Cơ chế: Sử dụng Queue (Hàng đợi - FIFO).
• Ứng dụng: Tìm đường đi ngắn nhất trên đồ thị không trọng số.

3. Bảng so sánh nhanh

include<bits></bits>

define ll long long

define ull unsigned long long

define ii pair

define fi first

define se second

define ass assign

define pb push_back

using namespace std;

mt1993764 rng(chrono::steadyclock::now().timesinceepoch().count());

void file(){ #define TASK "" if(fopen(TASK".INP","r")) freopen(TASK".INP","r",stdin), freopen(TASK".OUT","w",stdout); }

ll rand(ll l,ll r){ return rng()%(r-l+1)+l; }

const int N=1e5+5; const int LG=20;

struct Edge{ int u,v,idu,idv; };

int n,q; vector<pair>>adj[N]; Edge canh[N];</pair>

void init(){ cin>>n>>q; for(int i=1;i<n int u cin>>u>>v; adj[u].pb({v,1LL}); adj[v].pb({u,1ll}); canh[i]={u,v,(int)adj[u].size()-1,(int)adj[v].size()-1}; } }</n>

namespace sub{ bool check(){ return 1; }

int timer,sta[N],fin[N],depth[N],up[N][LG];

void dfs(int u,int p){
    sta[u]=++timer;
    up[u][0]=p;
    for(int i=1;i<LG;i++)
        up[u][i]=up[up[u][i-1]][i-1];
    for(pair<int,ll>pr:adj[u]){
        int v=pr.fi;
        ll w=pr.se;
        if(v==p)
            continue;
        depth[v]=depth[u]+1;
        dfs(v,u);
    }
    fin[u]=timer;
}

int lca(int u,int v){
    if(depth[u]<depth[v])
        swap(u,v);
    int diff=depth[u]-depth[v];
    for(int i=0;i<LG;i++)
        if((diff>>i)&1)
            u=up[u][i];
    if(u==v)
        return u;
    for(int i=LG-1;i>=0;i--)
        if(up[u][i]!=up[v][i]){
            u=up[u][i];
            v=up[v][i];
        }
    return up[u][0];
}

void solve(){
    dfs(1,0);
    while(q--){
        char opt;
        cin>>opt;
        if(opt=='I'){
            int r,s,t;
            cin>>r>>s>>t;
            if(canh[r].u<canh[r].v){
                adj[canh[r].u][canh[r].idv].se=s;
                adj[canh[r].v][canh[r].idu].se=t;

            }else{
                adj[canh[r].v][canh[r].idu].se=s;
                adj[canh[r].u][canh[r].idv].se=s;

            }
        }
        if(opt=='Q'){
            int x,y;
            cin>>x>>y;

        }
    }
}

}

int main(){ srand(time(NULL)); iosbase::syncwith_stdio(0); cin.tie(0);cout.tie(0); file();

init();
if(sub::check())
    sub::solve();

} /*

*/