https://vjudge.net/problem/UVA-506
题目是给出了五种指令，DEPEND、INSTALL、REMOVE、LIST、END，操作的格式及功能如下：
| DEPEND item1 item2 (item3 ...) | 安装item1需要先安装item2（、item3……） |
| INSTALL item1 | 安装item1，如果item1依赖其他组件，则先安装其依赖的其他组件 |
| REMOVE item1 | 移除item1及其依赖的全部组件，如果组件被其他程序依赖，则不移除 |
| LIST | 输出当前已安装的所有组件 |
| END | 结束程序 |
INSTALL指令中作为参数的组件的安装是显式安装，其所依赖的组件的安装不是显示安装。被显式安装的组件只能通过REMOVE指令显式删除，而移除中的组件如果当前被其他显式安装的组件直接或间接地依赖，则不能通过REMOVE移除。
每当输入指令之后，先原样输出一遍指令，然后执行指令。安装组件时如果可以安装组件则需输出“Installing 组建名”。如果显式安装时组件已被安装则提示“组建名 is already installed.”，隐式安装则无需提示。如果显式删除组件时组件未被安装则提示“组建名 is not installed.”，如果组件被其他组件依赖则提示“组建名 is still needed.”，隐式卸载则无需提示。
其实就是个用STL做的复杂模拟，纯属吃力不讨好的题目，并学不到什么算法思想，唯一的亮点就是为一个组件建立依赖和被依赖两个列表，其他的操作模拟即可。
1 #include <iostream> 2 #include <algorithm> 3 #include <string> 4 #include <sstream> 5 #include <set> 6 #include <vector> 7 #include <stack> 8 #include <map> 9 #include <queue> 10 #include <deque> 11 #include <cstdlib> 12 #include <cstdio> 13 #include <cstring> 14 #include <cmath> 15 #include <ctime> 16 #include <functional> 17 using namespace std; 18 19 int cnt = 0, status[maxn]; 20 vector<int> depend[maxn], depend2[maxn]; 21 vector<int> installed; 22 string name[maxn]; 23 24 int get_id(const string & x) 25 { 26 for (int i = 0; i < cnt; i++) 27 if (name[i] == x) 28 return i; 29 name[cnt++] = x; 30 return cnt-1; 31 } 32 33 void instal(int item, bool top) 34 { 35 if (!status[item]){ 36 for (size_t i = 0; i < depend[item].size(); i++) 37 instal(depend[item][i], false); 38 cout << " Installing " << name[item] << endl; 39 status[item] = top ? 1 : 2; 40 installed.push_back(item); 41 } 42 else if(top) 43 cout << " " << name[item] << " is already installed." << endl; 44 } 45 46 bool needed(int item) 47 { 48 for (size_t i = 0; i < depend2[item].size(); i++) 49 if (status[depend2[item][i]]) 50 return true; 51 return false; 52 } 53 54 void Remove(int item, bool top) 55 { 56 if(top && status[item]==0) 57 cout << " " << name[item] << " is not installed." << endl; 58 else if(top && needed(item)) 59 cout << " " << name[item] << " is still needed." << endl; 60 else if ((top || status[item] == 2) && !needed(item)){ 61 status[item] = 0; 62 installed.erase(remove(installed.begin(), installed.end(), item), installed.end()); 63 cout << " Removing " << name[item] << endl; 64 for (size_t i = 0; i < depend[item].size(); i++) 65 Remove(depend[item][i], false); 66 } 67 } 68 69 int main() 70 { 72 ios::sync_with_stdio(false); 73 string line; 74 while (getline(cin, line), line != "END") 75 { 76 cout << line << endl; 77 stringstream ss(line); 78 if (line[0] == ‘L‘){ 79 for (size_t i = 0; i != installed.size(); ++i) 80 cout << " " << name[installed[i]] << endl; 81 } 82 else{ 83 string t1, t2, t3; 84 ss >> t1 >> t2; 85 if (t1[0] == ‘D‘){ 86 while (ss >> t3){ 87 depend[get_id(t2)].push_back(get_id(t3)); 88 depend2[get_id(t3)].push_back(get_id(t2)); 89 } 90 } 91 else if (t1[0] == ‘I‘) 92 instal(get_id(t2), true); 93 else if (t1[0] == ‘R‘) 94 Remove(get_id(t2), true); 95 } 96 } 97 cout << "END" << endl; 98 return 0; 99 }
UVA 506 System Dependencies（模拟 烂题）
原文：http://www.cnblogs.com/YingZhixin/p/7512930.html