UVA 872 Ordering

UVA_872_Ordering.cpp

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

class Ordering {
private:
  bool toposort(string& dict, vector<string>& graph, vector<int>& indegrees, string& cache) {
    if (dict.length() == cache.length()) {
      cout << cache << endl;
      return true;
    }
    bool valid = false;
    for (char root : dict) {
      if (root == ' ') {
        continue;
      }
      if (indegrees[root] == 0) {
        indegrees[root]--;
        if (!cache.empty()) {
          cache.push_back(' ');
        }
        cache.push_back(root);
        string& nextset = graph[root];
        for (char next : nextset) {
          indegrees[next]--;
        }
        bool test = toposort(dict, graph, indegrees, cache);
        if (!test) {
          return false;
        }
        valid = true;
        cache.pop_back();
        if (!cache.empty()) {
          cache.pop_back();
        }
        indegrees[root]++;
        for (char next : nextset) {
          indegrees[next]++;
        }
      }
    }
    return valid;
  }
public:
  void solve(string& dict, vector<string>& graph, vector<int>& indegrees) {
    string cache = "";
    bool valid = toposort(dict, graph, indegrees, cache);
    if (!valid) {
      cout << "NO" << endl;
    }
  }
};

int main() {
  string line;
  getline(cin, line);
  int n = stoi(line);
  for (--n; n >= 0;--n) {
    getline(cin, line);
    getline(cin, line);
    string dict = line;
    getline(cin, line);

    vector<string> graph(256, "");
    vector<int> indegrees(256, 0);
    for (int i = 0; i < line.length(); i += 4) {
      graph[line[i]].push_back(line[i + 2]);
      indegrees[line[i + 2]]++;
    }
    Ordering().solve(dict, graph, indegrees);
    if (n > 0) {
      cout << endl;
    }
  }
  return 0;
}