Đếm số cây trong rừng (đồ thị không chu trình) C++

Cho đỉnh và danh sách cạnh của rừng (tập hợp các cây). Đếm số cây bằng DFS.

Ý tưởng

• Biểu diễn đồ thị bằng danh sách kề vector vec[V].
• Mảng check[V] đánh dấu đã thăm.
• Duyệt mọi đỉnh, nếu chưa thăm thì chạy DFS từ đỉnh đó và tăng đếm (một cây).

Ví dụ hoàn chỉnh

#include <bits/stdc++.h>
using namespace std;

void insert(vector<int> vec[], int parent, int child) {
    vec[parent].push_back(child);
    vec[child].push_back(parent);
}

void recurred(int temp, vector<int> vec[], vector<bool> &check) {
    check[temp] = true;
    int size = vec[temp].size();
    for (int i = 0; i < size; i++) {
        if (check[vec[temp][i]] == false)
            recurred(vec[temp][i], vec, check);
    }
}

int Trees_Forest(vector<int> vec[], int vertice) {
    int count = 0;
    vector<bool> check(vertice, false);
    for (int i = 0; i < vertice; i++) {
        if (check[i] == false) {
            recurred(i, vec, check);
            count++;
        }
    }
    return count;
}

int main() {
    int vertice = 9;
    vector<int> vec[vertice];
    insert(vec, 1, 3);
    insert(vec, 2, 8);
    insert(vec, 2, 6);
    insert(vec, 3, 5);
    insert(vec, 3, 7);
    insert(vec, 4, 8);
    cout << "Số cây trong rừng: " << Trees_Forest(vec, vertice);
    return 0;
}

Kết quả

Số cây trong rừng: 3