In Tất Cả Nút Lá Của Cây N-ary Bằng DFS Trong C++

Trong bài toán này, chúng ta được cho một mảng 2 chiều chứa các cạnh của cây n-ary, cạnh định nghĩa mối quan hệ cha-con. In tất cả nút lá của cây n-ary được tạo ra.

Cây n-ary là cây có tối đa n con, tức là một nút có thể có 1, 2, ... n nút con.

Ví dụ để hiểu vấn đề:

Đầu vào: edge[][] = {{5,8}, {5,6}, {8,1}, {8,4}, {6,7}} → Đầu ra: 1 4 7

Giải thích – Tạo cây từ mảng cạnh:

Các nút lá của cây này là 1, 4, 7.

Để giải quyết, ta duyệt cây bằng DFS (tìm nút lá của mỗi cây con). Đánh dấu nút đã thăm. Nếu nút có con (không phải lá), đặt cờ và in nút không có con.

Ví Dụ

Chương trình minh họa giải pháp:

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

void DFS(list<int> t[], int node, int parent) {
    int flag = 0;
    for (auto ir : t[node]) {
        if (ir != parent) {
            flag = 1;
            DFS(t, ir, node);
        }
    }
    if (flag == 0)
        cout << node << "\t";
}

int main() {
    list<int> t[1005];
    pair<int, int> edges[] = {
        { 1, 2 },
        { 1, 3 },
        { 2, 4 },
        { 3, 5 },
        { 3, 6 },
        { 3, 7 },
        { 6, 8 }
    };
    int cnt = sizeof(edges) / sizeof(edges[0]);
    int node = cnt + 1;
    for (int i = 0; i < cnt; i++) {
        t[edges[i].first].push_back(edges[i].second);
        t[edges[i].second].push_back(edges[i].first);
    }
    cout << "Các nút lá của cây là:\n";
    DFS(t, 1, 0);
    return 0;
}

Đầu Ra

Các nút lá của cây là: 4 5 8 7