UVa 11060 Becerages

想法：
　　記錄每個點被其他點連入的數量(Ex: A->B, C->B，則beConnected[B]=2)，和記錄各個點連到哪些點。

1. 每次從頭找beConnected[i]==0(表示沒有點連到i)的Node
2. 將這個Node輸出
3. 同時將beConnected[i]改成-1表示這Node已經輸出過了
4. 然後其他每個被Node i連入的Node j，把beConnected[j]--
5. 執行1~4 N次，把每個Node都輸出過

	#include <iostream>
	#include <string>
	#include <map>
	#include <vector>
	using namespace std;
	map<string, int> Map;
	string Name[105];
	vector<int> toNxt[105];
	int beConnected[105]; //該node被其他點連入的數量
	void Initial(int N)
	{
	Map.clear();
	for (int i = 0; i < N; ++i) {
	toNxt[i].clear();
	beConnected[i] = 0;
	}
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	ios::sync_with_stdio(false);
	int N, M, Case = 1;
	string s1, s2;
	while (cin >> N) {
	Initial(N);
	for (int i = 0; i < N; ++i)
	cin >> s1, Map[s1] = i, Name[i] = s1;
	cin >> M;
	for (int i = 0; i < M; ++i) {
	cin >> s1 >> s2;
	toNxt[Map[s1]].push_back(Map[s2]);
	++beConnected[Map[s2]];
	}
	cout << "Case #" << Case++ << ": Dilbert should drink beverages in this order:";
	for (int i = 0; i < N; ++i) {
	int pos = 0;
	while (beConnected[pos] != 0) ++pos;
	beConnected[pos] = -1;
	cout << ' ' << Name[pos];
	for (int nxt : toNxt[pos])
	--beConnected[nxt];
	}
	cout << '.' << endl << endl;
	}
	}

view raw [UVa] 11060 Beverages.cpp hosted with ❤ by GitHub