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;
}