https://algospot.com/judge/problem/read/DICTIONARY#
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 | #include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; vector<string> words; vector<vector<int> > adj; vector<int> seen, order; int C; int N; void makeGraph(const vector<string>& words){ adj = vector<vector<int> >(26, vector<int>(26, 0)); for(int j = 1; j < words.size(); ++j){ int i = j-1; int len = min(words[i].size(), words[j].size()); for(int k = 0; k < len; ++k){ if(words[i][k] != words[j][k]){ int a = words[i][k] - 'a'; int b = words[j][k] - 'a'; adj[a][b] = 1; break; } } } } void dfs(int here){ seen[here] = 1; for(int there = 0; there < adj.size(); ++there) if(adj[here][there] && !seen[there]) dfs(there); order.push_back(here); } vector<int> topologicalSort(){ int n = adj.size(); seen = vector<int>(n, 0); order.clear(); for(int i = 0; i < n; ++i) if(!seen[i]) dfs(i); reverse(order.begin(), order.end()); for(int i = 0; i < n; ++i) for(int j = i + 1; j < n; ++j) if(adj[order[j]][order[i]]) return vector<int>(); return order; } int main(){ cin >> C; for(int j = 0; j < C; j++){ cin >> N; words.clear(); for(int i = 0; i < N; i++){ string temp; cin >> temp; words.push_back(temp); } makeGraph(words); vector<int> arr = topologicalSort(); /*for(int j = 0; j < adj.size(); j++){ for(int i = 0; i < adj.size(); i++){ cout << adj[j][i] << " "; } cout << endl; }*/ if(arr.empty()) cout << "INVALID HYPOTHESIS" << endl; else{ for(int i = 0; i < arr.size(); i++){ //cout << arr[i] << " "; char temp; temp = (char)(arr[i] + 'a'); cout << temp; } cout << endl; } } return 0; } | cs |