UVa 11606 Pick up sticks

想法：

    把放在最上面(也就是這個點沒有其他點連入)的stick當做起點，用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);
	}

view raw [UVa] 200 Rare Order.cpp hosted with ❤ by GitHub