Programming學習筆記: UVa 200 Rare Order

2014年3月7日星期五

UVa 200 Rare Order

題意：
　　Input給的那些字串是每個index的名稱，而這些Index是照"某個字典序"由小到大排好的(就像一般的目錄是從A~Z排好)，我們要從Input裡面判斷這些字的字典序。例如Sample Input：
XWY
ZX
ZXY
ZXW
YWWX
我們可以從XWY和ZX判斷X<Z，ZXY和ZXW判斷Y<W，ZXW和YWWX判斷Z<Y，所以可以得到X<Z<Y<W。

**本題測資只有一個**

想法：
　　一次兩行判斷，找出誰<誰，記錄完之後，從沒有被連入的點當做起點，使用DFS走遍並記下走遍的點，將記下的點逆向輸出就是一個topological sort。

	#include <iostream>
	#include <cstdio>
	#include <string>
	#include <vector>
	using namespace std;

	vector<char> ans;
	vector<char> toPoint[100];
	int visit[100] = {0};
	int deg[100] = {0}; // deg[i]=1:沒有被其他點連入 deg[i]=2:被其他點連入
	void DFS(char n);

	int main()
	{
	// freopen("input.txt","rt",stdin);
	ios::sync_with_stdio(false);
	string a, b;
	cin >> a;
	while (cin >> b && b != "#") {
	int L = (a.size() > b.size()) ? b.size() : a.size();
	for (int i = 0; i < L; ++i) {
	if (deg[a[i]] == 0) deg[a[i]] = 1;
	if (deg[b[i]] == 0) deg[b[i]] = 1;
	if (b[i] != a[i]) {
	toPoint[a[i]].push_back(b[i]);
	deg[b[i]] = 2;
	break;
	}
	}
	a = b;
	}
	for (char i = 'A'; i <= 'Z'; ++i)
	if (deg[i] == 1)
	DFS(i);

	for (auto iter = ans.rbegin(); iter != ans.rend(); ++iter)
	cout << *iter;
	cout << endl;
	}
	void DFS(char n)
	{
	if (visit[n] == 1) return;
	visit[n] = 1;

	for (char nxt : toPoint[n])
	if (visit[nxt] != 2)
	DFS(nxt);
	visit[n] = 2;
	ans.push_back(n);
	}