506 - System Dependencies （UVA）-CSDN博客

本文链接：https://blog.csdn.net/linh2006/article/details/135463018

这篇文章介绍了解决一个编程问题，涉及到在OnlineJudge平台上处理组件的安装和移除操作，遵循拓扑排序原则，确保explicitlyinstalled组件不能被implicitlyremoved。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目链接如下：

Online Judge

这道题有个小细节，explicitly installed的component，不能被implicitly removed.

有一点拓扑排序的思想，用in[component]代表目前depend on在这个component上的component数量。

我的代码如下：

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <sstream>
// #define debug

struct node{
    std::string str;
    bool expli;
    bool exist = true;
    node(std::string _str): str(_str){}
};
std::string line, op, u, v;
std::map<std::string, int> in;
std::map<std::string, std::vector<std::string>> dep;
std::set<std::string> st;
std::vector<node> vec;
std::map<std::string, int> mp;

void install(std::string str, bool flag){
    for (int i = 0; i < dep[str].size(); ++i){
        if (st.find(dep[str][i]) == st.end()){
            install(dep[str][i], false);
        }
        in[dep[str][i]]++;
    }
    printf("   Installing %s\n", str.c_str());
    st.insert(str);
    mp[str] = vec.size();
    vec.push_back(node(str));
    vec.back().expli = flag;
}

void remove(std::string str){
    printf("   Removing %s\n", str.c_str());
    st.erase(str);
    vec[mp[str]].exist = false;
    for (int i = 0; i < dep[str].size(); ++i){
        in[dep[str][i]]--;
        if (!in[dep[str][i]] && !vec[mp[dep[str][i]]].expli){
            remove(dep[str][i]);
        }
    }
}

int main(){
    #ifdef debug
    freopen("0.txt", "r", stdin);
    freopen("1.txt", "w", stdout);
    #endif
    while (getline(std::cin, line)){
        in.clear();
        dep.clear();
        st.clear();
        vec.clear();
        mp.clear();
        do {
            printf("%s\n", line.c_str());
            std::stringstream ss(line);
            ss >> op;
            if (op == "LIST"){
                for (int i = 0; i < vec.size(); ++i){
                    if (vec[i].exist){
                        printf("   %s\n", vec[i].str.c_str());
                    }
                }
            } else {
                ss >> u;
                if (op == "DEPEND"){
                    while (ss >> v){
                        dep[u].push_back(v);
                    }
                } else if (op == "INSTALL"){
                    if (st.find(u) != st.end()){
                        printf("   %s is already installed.\n", u.c_str());
                    } else {
                        install(u, true);
                    }
                } else if (op == "REMOVE"){
                    if (st.find(u) == st.end()){
                        printf("   %s is not installed.\n", u.c_str());
                    } else if (in[u]) {
                        printf("   %s is still needed.\n", u.c_str());
                    } else {
                        remove(u);
                    }
                }
            }
            getline(std::cin, line);
        } while (line[0] != 'E');
        printf("%s\n", line.c_str());
    }
    #ifdef debug
    fclose(stdin);
    fclose(stdout);
    #endif
    return 0;
}