题目描述题目要求模拟软件组件的安装和移除过程。每个组件可能有依赖关系必须预先安装其他组件。安装命令可以显式或隐式安装组件移除命令只能移除不再被需要的组件。需要根据命令执行相应的操作并输出结果。输入格式输入包含若干命令每行一个命令。命令类型有DEPEND item1 item2 [item3 ...]定义依赖关系item1item1item1依赖于item2item2item2、item3item3item3等。INSTALL item安装itemitemitem及其依赖若尚未安装。REMOVE item移除itemitemitem若未被其他组件依赖且不是显式安装。LIST列出所有已安装的组件按安装顺序。END结束当前测试用例。组件名称不超过101010个字符区分大小写。依赖关系在INSTALL之前定义无循环依赖。输入以END结束。输出格式对于每个命令先原样输出命令本身。对于INSTALL和REMOVE输出执行的动作每行以三个空格开头。对于LIST输出所有已安装组件每行以三个空格开头。对于DEPEND和END不输出额外内容。具体输出格式见样例。样例输入DEPEND TELNET TCPIP NETCARD DEPEND TCPIP NETCARD DEPEND DNS TCPIP NETCARD DEPEND BROWSER TCPIP HTML INSTALL NETCARD INSTALL TELNET INSTALL foo REMOVE NETCARD INSTALL BROWSER INSTALL DNS LIST REMOVE TELNET REMOVE NETCARD REMOVE DNS REMOVE NETCARD INSTALL NETCARD REMOVE TCPIP REMOVE BROWSER REMOVE TCPIP END输出DEPEND TELNET TCPIP NETCARD DEPEND TCPIP NETCARD DEPEND DNS TCPIP NETCARD DEPEND BROWSER TCPIP HTML INSTALL NETCARD Installing NETCARD INSTALL TELNET Installing TCPIP Installing TELNET INSTALL foo Installing foo REMOVE NETCARD NETCARD is still needed. INSTALL BROWSER Installing HTML Installing BROWSER INSTALL DNS Installing DNS LIST NETCARD TCPIP TELNET foo HTML BROWSER DNS REMOVE TELNET Removing TELNET REMOVE NETCARD NETCARD is still needed. REMOVE DNS Removing DNS REMOVE NETCARD NETCARD is still needed. INSTALL NETCARD NETCARD is already installed. REMOVE TCPIP TCPIP is still needed. REMOVE BROWSER Removing BROWSER Removing HTML Removing TCPIP REMOVE TCPIP TCPIP is not installed. END题目分析本题的核心是维护组件的依赖关系和安装状态模拟安装和移除过程。数据结构explicitly记录显式安装的组件。installed记录已安装的组件及其安装序号。sequence按安装序号存储组件名称。depend每个组件的依赖列表。referencedBy每个组件被哪些组件依赖。安装逻辑递归安装组件的所有依赖先依赖后自身。若组件已安装则跳过。显式安装的组件标记为显式。移除逻辑若组件未被任何其他组件依赖且不是显式安装或允许隐式移除则可移除。移除后递归检查其依赖是否可移除。命令处理DEPEND记录依赖关系。INSTALL若已安装则输出already installed否则调用安装函数。REMOVE若未安装则输出not installed若仍被需要则输出still needed否则调用移除函数。LIST按安装顺序输出所有组件。复杂度分析每个命令处理复杂度O(依赖数)O(\text{依赖数})O(依赖数)总复杂度可接受。代码实现// System referredencies// UVa ID: 506// Verdict: Accepted// Submission Date: 2017-04-25// UVa Run Time: 0.000s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intindexer0;// index of itemsmapstring,boolexplicitly;// explicitly installed itemsmapstring,intinstalled;// installed items include explicitly and implicitlymapint,stringsequence;// installed items with ordermapstring,vectorstringdepend;// item1 depends item2, item3, ...mapstring,setstringreferencedBy;// item1 referenced by item2, item3, ...voidinstall(string software,booltopmost){for(autocomponent:depend[software]){referencedBy[component].insert(software);install(component,false);}if(installed.find(software)installed.end()){cout Installing software\n;installed.insert(make_pair(software,indexer));sequence.insert(make_pair(indexer,software));indexer;if(topmost)explicitly[software]true;}}voidremove(string software,booltopmost){if((topmost||!explicitly[software])referencedBy[software].size()0){cout Removing software\n;sequence.erase(installed[software]);installed.erase(software);referencedBy.erase(software);if(topmost)explicitly[software]false;for(autocomponent:depend[software]){referencedBy[component].erase(software);if(referencedBy[software].size()0!explicitly[software])remove(component,false);}}}voidparse(string line){string action,software,component;istringstreamiss(line);issaction;if(actionDEPEND){isssoftware;while(isscomponent)depend[software].push_back(component);}elseif(actionINSTALL){isssoftware;if(installed.find(software)!installed.end())cout software is already installed.\n;elseinstall(software,true);}elseif(actionREMOVE){isssoftware;if(installed.find(software)installed.end())cout software is not installed.\n;else{if(referencedBy[software].size()0)cout software is still needed.\n;elseremove(software,true);}}elseif(actionLIST){for(autos:sequence)cout s.second\n;}}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);string line;while(getline(cin,line)){if(line!END){do{coutline\n;if(lineEND)break;parse(line);}while(getline(cin,line));}indexer0;explicitly.clear();installed.clear();sequence.clear();depend.clear();referencedBy.clear();}return0;}