UVa 872 Ordering

想法：
    這題是backtracking內融合了topological sort，基本上就是第一格, 第二格, ....依序填入，每次填的時後判斷哪些node可以填(表示需要在該node前出現的node已經出現過了)，詳細見底下code。

	#include <iostream>
	#include <string>
	#include <vector>
	#include <sstream>
	#include <algorithm>
	using namespace std;
	int Input(char []);
	void Input2(char [], vector<int> [], int []);
	bool backtracking(int, int, vector<int> [], int [], vector<int> &, char []);
	int main()
	{
	ios::sync_with_stdio(false);
	int Case;
	cin >> Case;
	while (Case--) {
	char Node_Name[30]; // 存每個Node的名稱('A','B',...)
	vector<int> toNxt[30]; // toNxt[i]表示i在哪些node的前面
	int beConnected[30] = {0}; // beConnected[i]表示有多少node在i前面
	vector<int> Container; // backtracking存答案用
	// Input用來讀這個Case的第一行, Input2用來讀第二行
	int N = Input(Node_Name); // N表示這個Case有幾個node
	sort(Node_Name, Node_Name + N); // 題目要求解答是字典序
	Input2(Node_Name, toNxt, beConnected);
	if (! backtracking(N, 0, toNxt, beConnected, Container, Node_Name))
	cout << "NO" << endl;
	if (Case) cout << endl;
	}
	}
	int Input(char Node[])
	{
	int n = 0;
	stringstream SS;
	string Str;
	while (getline(cin, Str) && Str.empty());
	SS << Str;
	while (SS >> Node[n]) ++n;
	return n;
	}
	int find_position(char a, char Node_Name[])
	{
	for (int i = 0; ; ++i)
	if (a == Node_Name[i])
	return i;
	}
	void Input2(char Node_Name[], vector<int> toNxt[], int beConnected[])
	{
	stringstream SS;
	string Str;
	while (getline(cin, Str) && Str.empty());
	SS << Str;
	while (SS >> Str) {
	int a = find_position(Str[0], Node_Name);
	int b = find_position(Str[2], Node_Name);
	toNxt[a].push_back(b);
	++beConnected[b];
	}
	}
	bool backtracking(int N, int Len, vector<int> toNxt[],
	int beConnected[], vector<int> &Container, char Node[])
	{
	if (Len == N){
	cout << Node[Container[0]];
	for (int i = 1; i < N; ++i)
	cout << ' ' << Node[Container[i]];
	cout << endl;
	return true;
	}
	bool ok ,hasAns = false;
	for (int i = 0; i < N; ++i) {
	if (beConnected[i] == 0) {
	Container.push_back(i); // 將i放入解答
	--beConnected[i]; // 避免等等又選到i
	for (int nxt : toNxt[i])
	--beConnected[nxt]; // 將i連到的node --
	ok = backtracking(N, Len + 1, toNxt, beConnected, Container, Node);
	if (ok) hasAns = true;
	Container.pop_back();
	++beConnected[i];
	for (int nxt : toNxt[i])
	++beConnected[nxt];
	}
	}
	return hasAns;
	}

view raw [UVa] 872 Ordering.cpp hosted with ❤ by GitHub