dfs.cpp

Bài toán

Duyệt theo chiều sâu (DFS), và in ra thời gian thăm của các nút.

Độ phức tạp

O(n+m

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

#define N 100005

int n, m, cnt;

vector<int> a[N];

int Visited[N], Parent[N];

void visit(int u) {

    cout << "Visiting " << u << endl;

    Visited[u] = ++cnt; // travesal time

    for (int i = 0; i < a[u].size(); i++) {

        int v = a[u][i];

        if (v != Parent[u]) {

            if (!Visited[v]) {

                Parent[v] = u;

                visit(v);

            }

        }

    }

}

int main() {

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {

        int p, q;

        cin >> p >> q;

        /*do {

            p=rand()%n+1;

            q=rand()%n+1;

        } while (p==q);

        cout << p << " " << q << endl;*/

        a[p].push_back(q);

        a[q].push_back(p);

    }

    for (int i = 1; i <= n; i++) if (!Visited[i]) visit(i);

    cout << "Travesal time: " << endl;

    for (int i = 1; i <= n; i++) cout << Visited[i] << " ";

    cout << endl;

    cin.ignore(2);

}

Nhận xét

Ví dụ

6 10

6 5

5 3

2 4

2 6

2 3

4 1

4 1

3 4

4 3

3 6

Visiting 1

Visiting 4

Visiting 2

Visiting 6

Visiting 5

Visiting 3

Travesal time:

1 3 6 2 5 4