M27928: 遍历树

adjacency list, dfs, http://cs101.openjudge.cn/practice/27928/

思路：对每个节点，将它与所有子节点的值一起按从小到大排序，先递归遍历比它小的子节点，最后输出自己，这样整棵树按规则完成遍历。

#include <iostream>
#include <map>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

void dfs(int u, map<int, vector<int>>& son) {

    vector<int> tmp = son[u];
    tmp.push_back(u);
    sort(tmp.begin(), tmp.end());
    
    for (int v : tmp) {
        if (v == u) {
            cout << u << "\n";  
        } else {
            dfs(v, son);       
        }
    }
}

int main() {
    int n;
    cin >> n;

    map<int, vector<int>> son;  
    set<int> all_nodes;         
    set<int> non_roots;         


    for (int i = 0; i < n; ++i) {
        int parent;
        cin >> parent;
        all_nodes.insert(parent);
        string line;
        getline(cin, line);  
        int num = 0;
        bool has_num = false;


        for (char c : line) {
            if (isdigit(c)) {
                num = num * 10 + (c - '0');
                has_num = true;
            } else if (has_num) {
                son[parent].push_back(num);
                non_roots.insert(num);
                all_nodes.insert(num);
                num = 0;
                has_num = false;
            }
        }
        if (has_num) { 
            son[parent].push_back(num);
            non_roots.insert(num);
            all_nodes.insert(num);
        }
    }


    vector<int> roots;
    for (int x : all_nodes)
        if (!non_roots.count(x))
            roots.push_back(x);

    sort(roots.begin(), roots.end());


    for (int r : roots)
        dfs(r, son);

    return 0;
}

思路：需要用 getline 一行行读取数据, 且题目没有给出根节点, 以及节点的顺序不固定, 因此用 unordered_map 邻接表存储树, 建树并找到根结点后遍历即可

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

// 用邻接表存储树结构
unordered_map<int, vector<int>> tree;

void dfs(int root) {
    vector<int> children = tree[root];
    children.push_back(root);
    sort(children.begin(), children.end());

    for (int child : children) {
        if (child == root) {
            cout << root << '\n';
        } else {
            dfs(child);
        }
    }
}

int main() {
    int n;
    cin >> n;
    string line;
    getline(cin, line); // 读取剩余的换行符
    unordered_set<int> child;
    unordered_set<int> all_nodes;
    
    for (int i = 0; i < n; i++) {
        getline(cin, line);
        stringstream ss(line);  // 初始化 stringstream 对象
        int u, v;
        ss >> u;
        all_nodes.insert(u);
    
        while (ss >> v) {
            tree[u].push_back(v);
            child.insert(v);
        }
    }

    // 找到根节点
    int root = -1;
    for (int node : all_nodes) {
        if (child.count(node) == 0) {
            root = node;
            break;
        }
    }

    dfs(root);
}