Comment

Huhu_Miao: 2025-01-01 10:12:42

/**
 *    author:  Huhu_Miao
 *    created: 2025.1.1 10:09:00 (UTC+8)
 *    致敬传奇数组rootChildren
**/

#include <iostream>
#include <vector>
#include <deque>
#include <string>
#include <algorithm>
#include <map>
#include <set>

void print(int depth, const std::string &str){
    for(int i = 0; i < depth; i++) std::cout << "****";
    std::cout << str << '\n';
}

void dfs(const std::vector<std::vector<int>> &g, 
    std::deque<bool> &vis, int node, int depth, 
    const std::map<int,std::string> &myMap){
    if(vis[node]) return;

    vis[node] = true;
    print(depth, myMap.at(node));

    for(int child : g[node]){
        if(!vis[child]){
            depth++;
            dfs(g, vis, child, depth, myMap);
            depth--;
        }
    }   
}

void solve(){
    int n;
    std::cin >> n;

    std::map<int,std::string> myMap;

    for(int i = 0; i < n; i++){
        int num;
        std::string str;
        std::cin >> num >> str;
        myMap[num] = str;
    }

    int m;
    std::cin >> m;
    std::vector<std::vector<int>> g(n + 1);
    std::set<int> childSet;

    for(int i = 0; i < m; i++){
        int father, child;
        std::cin >> father >> child;
        g[father].push_back(child);
        childSet.insert(child);
    }

    for(auto & adj : g) std::sort(adj.begin(), adj.end());

    std::vector<int> rootChildren;
    for(const auto &p : myMap){
        int id = p.first;
        if(!childSet.count(id)) rootChildren.push_back(id);
    }

    std::sort(rootChildren.begin(), rootChildren.end());

    std::deque<bool> vis(n + 1, false);

    std::cout << "root\n";

    for(int rootId : rootChildren) if(!vis[rootId]) dfs(g, vis, rootId, 1, myMap);
}

int main(){
    std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
    int T; std::cin>>T;
    while(T--) solve();
    return 0;
}

Huhu_Miao: 2025-01-01 09:55:46

不完整建树就过不去，不知道样例里掺什么东西了。

9999999999: 2025-01-01 09:45:04

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <queue>

static const int INDENT_PER_LEVEL = 4;
using namespace std;

struct FileNode {
    int id;
    string name;
    vector<int> children;
};

class FileSystem {
public:
    void readInput() {
        cin >> n;
        fileNodes.reserve(n);

        for (int i = 0; i < n; i++) {
            int id;
            string filename;
            cin >> id >> filename;
            idToName[id] = filename;
            allIds.push_back(id);
        }

        cin >> m;
        for (int i = 0; i < m; i++) {
            int parentId, childId;
            cin >> parentId >> childId;
            parentToChildren[parentId].push_back(childId);
            nonRootSet.insert(childId);
        }

        for (auto& pair : parentToChildren) {
            sort(pair.second.begin(), pair.second.end());
        }

        for (auto id : allIds) {
            if (nonRootSet.find(id) == nonRootSet.end()) {
                rootChildren.push_back(id);
            }
        }
        sort(rootChildren.begin(), rootChildren.end());

        buildFileNodes();
    }

    void print() const {
        cout << "root\n";
        for (auto id : rootChildren) {
            dfsPrint(id, INDENT_PER_LEVEL);
        }
    }

private:
    void buildFileNodes() {
        fileNodes.clear();
        fileNodes.resize(n + 1);

        for (auto& pair : idToName) {
            if (pair.first >= 0 && pair.first < static_cast<int>(fileNodes.size())) {
                fileNodes[pair.first].id = pair.first;
                fileNodes[pair.first].name = pair.second;
            }
        }

        for (auto& pair : parentToChildren) {
            if (pair.first >= 0 && pair.first < static_cast<int>(fileNodes.size())) {
                for (auto cid : pair.second) {
                    if (cid >= 0 && cid < static_cast<int>(fileNodes.size())) {
                        fileNodes[pair.first].children.push_back(cid);
                    }
                }
            }
        }
    }

    void dfsPrint(int curId, int level) const {
        for (int i = 0; i < level; i++) {
            cout << "*";
        }
        cout << idToName.at(curId) << '\n';

        if (parentToChildren.find(curId) != parentToChildren.end()) {
            for (auto childId : parentToChildren.at(curId)) {
                dfsPrint(childId, level + INDENT_PER_LEVEL);
            }
        }
    }

private:
    int n = 0;
    int m = 0;
    vector<int> allIds;
    vector<int> rootChildren;
    unordered_map<int, string> idToName;
    unordered_map<int, vector<int>> parentToChildren;
    unordered_set<int> nonRootSet;
    vector<FileNode> fileNodes;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        FileSystem fs;
        fs.readInput();
        fs.print();
    }

    return 0;
}