UVA506 系统依赖 System Dependencies,

  1. 使用一个vector和map实现将string 组件名字映射成为int类型
  2. 指令DEPEND：反正就是整个规则的记录，组件依赖什么，在进行安装的时候，就参照对应的depend将所有依赖的组件进行安装，很明显要先将依赖安装，所以整个安装是一个递归，然后用一个statue数组来记录，对应i对象(名字和int的映射)是否已经被安装。。。。
  3. ;Remove指令，要判断，能不了进行删除，然后删除并删除其对应依赖的组件，如果依赖其依赖组件还有需要支持的组件存在，就不可以删掉的，所有在一开始记录整个规则的时候要还加一个depend2数组，记录这个组件支持什么，然后看status数组，看看需要他支持的还有没有，然后先删除item再他的依赖，很明显是递归，只是这是先删自己再删依赖
  4. ;然后还有一个注意的就是，所有显式装的都是不可以隐式地被卸载

代码

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#define LOCAL
const int maxn = 10000;
using namespace std;
vector depend[maxn], depend2[maxn];
vector componentname;
map componentid;
vector installed;
int status[maxn];

int ID(string item) {
	if (!componentid.count(item)) {
		componentname.push_back(item);
		componentid[item] = componentname.size() - 1;
	}
	return componentid[item];
}

bool needed(int item) {
	for (int i = 0; i < depend2[item].size(); i++) 
		if (status[depend2[item][i]] > 0) return true;
	return false;
}

void remove(int item,bool explicitly) {
	if (!needed(item) && (explicitly || status[item] == 2)) {
		cout << "   " << "Removing " << componentname[item] << endl;
		status[item] = 0;
		installed.erase(remove(installed.begin(), installed.end(), item), installed.end());
		for (int i = 0; i < depend[item].size(); i++)
			remove(depend[item][i], false);
	}
}

void install(int index, bool explicitly) {
	if (status[index] > 0) return;
	for (int i = 0; i < depend[index].size(); i++)
		install(depend[index][i], false);
	installed.push_back(index);
	status[index] = ((explicitly == true) ? 1 : 2);
	cout <<"   Installing "<< componentname[index] << endl;
	return;
}

void list() {
	for (int i = 0; i < installed.size(); i++)
		cout << "   " << componentname[installed[i]] << endl;
}

int main() {
#ifdef LOCAL
	freopen("output.txt", "w", stdout);
#endif // LOCAL

	string line, cmd;
	memset(status, 0, sizeof(status));
	while (getline(cin, line)) {
		stringstream ss(line);
		ss >> cmd;
		cout << line << endl;
		if (cmd[0] == 'E') break;
		else if (cmd[0] == 'L') list();
		else{
			string item1, item2;
			ss >> item1;
			int it1 = ID(item1);
			if (cmd[0] == 'I') { 
				if (status[it1] > 0) cout << "   " << item1 << " is already installed." << endl;
				else install(ID(item1), true); 
			}
			else if (cmd[0] == 'R') { 
				if (status[it1] == 0) cout << "   " << item1 << " is not installed."<< endl;
				else if (needed(it1)) cout << "   " << item1 << " is still needed."<< endl;
				else remove(it1, true); 
			}
			else {
				while (ss >> item2) {
					int it2 = ID(item2);
					depend[it1].push_back(it2);
					depend2[it2].push_back(it1);
				}
			}
		}
	}

	return 0;
}
刷题

相关

2017 清北济南考前刷题Day 6 morning

面试随缘刷题--day7

C语言刷题笔记6

LeetCode刷题总结-数组篇（上）

C语言刷题笔记5

C语言刷题笔记4

[整理]qbxt周末刷题班 Day2总结

刷题记录——疫情问答积分（模拟）

Leetcode 刷题小抄 Java版

LeetCode刷题之DP算法

力扣每天刷题(2)

free code camp 刷题记录 js(ES6 箭头函数)

标签