Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

Problem Statement We found a dictionary of the Ancient Civilization Mayo (ACM) during…

  1. User

    Problem Statement

    We found a dictionary of the Ancient Civilization Mayo (ACM) during excavation of the ruins. After analysis of the dictionary, we revealed they used a language that had not more than 26 letters. So one of us mapped each letter to a different English alphabet and typed all the words in the dictionary into a computer.

    How the words are ordered in the dictionary, especially whether they are ordered lexicographically, is an interesting topic to many people. As a good programmer, you are requested to write a program to judge whether we can consider the words to be sorted in a lexicographical order.

    Note: In a lexicographical order, a word always precedes other words it is a prefix of. For example, ab precedes abc, abde, and so on. Input

    The input consists of multiple datasets. Each dataset is formatted as follows:

    n string_1 ... string_n

    Each dataset consists of n+1 lines. The first line of each dataset contains an integer that indicates n (1 \leq n \leq 500). The i-th line of the following n lines contains string_i, which consists of up to 10 English lowercase letters.

    The end of the input is 0, and this should not be processed.

    Output

    Print either yes or no in a line for each dataset, in the order of the input. If all words in the dataset can be considered to be ordered lexicographically, print yes. Otherwise, print no.

    Example

    Input

    4 cba cab b a 3 bca ab a 5 abc acb b c c 5 abc acb c b b 0

    Output

    yes no yes no

  2. DeepSeek Assistant

    We need to solve: Given a list of words, determine if there exists a permutation of the alphabet (i.e., a total order on letters) such that the list is sorted lexicographically according to that order, where lexicographic order also respects the prefix rule: a word that is a prefix of another comes before the longer word.

    We are told: The ancient language used not more than 26 letters, and each letter is mapped to a distinct English alphabet (so a bijection from the ancient alphabet to English letters; but we only see the mapped words, using English letters. The mapping is unknown. So we need to check if we can assign a total order to the 26 English letters (or at least to the ones appearing) such that the given sequence is lexicographically non-decreasing? Actually "ordered lexicographically" means the words are sorted in ascending order according to that order. So we need to check if there exists a total order on letters (a permutation of the 26 letters) such that for every consecutive pair (word_i, word_{i+1}), we have word_i <= word_{i+1} in lexicographic order using that custom ordering, and also the ordering respects the prefix rule automatically (i.e., if one word is a prefix of the other, the shorter must come before the longer; but that is a property of lexicographic order: a prefix is considered less than any longer string that starts with that prefix). However, note: In standard lexicographic order, if we have a custom alphabet order, the rule that a prefix comes before any longer extension still holds. Because when comparing two strings, we compare character by character; if we reach the end of one, that one is smaller. So it's inherent. So we don't need to impose an extra rule; it's part of lexicographic comparison.

    But careful: The problem statement says: "In a lexicographical order, a word always precedes other words it is a prefix of. For example, ab precedes abc, abde, and so on." This is just a reminder of how lexicographic order works. So we just need to check if there exists a total order on letters such that the given list is sorted in non-decreasing order according to that order.

    However, there is nuance: The mapping from ancient letters to English letters is one-to-one, but the English letters are just placeholders. So we can assign any total order to the set of letters appearing (and any ordering among unused letters doesn't matter). So it's a classic problem: given a set of constraints from pairwise string comparisons, can we assign a linear order to letters that satisfies them?

    But note: The input words are "typed into a computer" after mapping each ancient letter to a different English alphabet. That means each English letter represents a distinct ancient letter. However, the mapping is arbitrary; we don't know which English letter corresponds to which ancient letter. But we can assign any ordering to the English letters; there is no inherent order. So we need to see if we can assign an order such that the sequence is sorted.

    The problem essentially: Given a sequence of strings, is there a total order on the alphabet (the 26 letters) that makes the sequence non-decreasing in lexicographic order?

    This is analogous to determining if there exists a permutation (order) that satisfies constraints derived from comparing consecutive strings. The constraints are of the form: for each i, either the strings are identical (then no constraint, since equal is okay, but careful: if they are identical, it's fine; but also need to consider if prefix rule? Actually identical words are allowed; they are equal, so order doesn't matter). If they differ at the first differing character, then we need that the character in word_i is less than the character in word_{i+1} according to the unknown order. If word_i is a prefix of word_{i+1}, then word_i < word_{i+1} automatically regardless of the order (since we compare and run out of characters in the first). This imposes no constraint on letters. Similarly, if word_{i+1} is a prefix of word_i, then word_i > word_{i+1}, which would violate non-decreasing order unless the words are equal? Actually if word_{i+1} is a prefix of word_i, then when comparing word_i and word_{i+1}, we would find that word_{i+1} ends first, so word_{i+1} < word_i. For the sequence to be non-decreasing, we need word_i <= word_{i+1}. So if word_{i+1} is a prefix of word_i, then we have word_i > word_{i+1}, which is a violation regardless of the letter order. However, is it possible that the words are equal? No, because one is a proper prefix. So this condition would immediately make the answer "no". But wait: Could there be a scenario where the order of letters could make word_i <= word_{i+1} even if word_i is longer and shares the prefix? No, because the lexicographic comparison rule is defined based on the ordering of characters, but when one string is a prefix of the other, the shorter string is always considered smaller, regardless of the character order. So if word_i is longer and word_{i+1} is a prefix (i.e., word_{i+1} is shorter and matches the beginning of word_i), then word_i > word_{i+1} inevitably. So that would violate the ordering. So we can check that: for each consecutive pair, if word_{i+1} is a prefix of word_i (strictly), then it's impossible -> answer no.

    But what about the case where word_i is a prefix of word_{i+1}? That is fine; it imposes no constraints.

    If they are not prefix-related and differ at some position, let k be the first index where the two strings differ, with characters c1 from word_i and c2 from word_{i+1}. Then to have word_i <= word_{i+1}, we need c1 < c2 in the custom order (c1 cannot be equal because they differ). So we add a constraint: c1 < c2.

    We then need to check if there exists a total order (i.e., a linear extension) of the partial order defined by these constraints that is consistent (i.e., no cycles). Since we have up to 500 words, each up to length 10, number of constraints is at most n-1. Letters are 26, so we can perform a topological sort check for cycles. However, we must also consider that we have 26 distinct letters, but constraints only involve some letters. There's no requirement that the mapping must be bijective among all 26? Actually the mapping is from ancient alphabet to English letters, each ancient letter maps to a distinct English letter. But there may be fewer than 26 distinct letters in the dictionary. The unused letters can be arbitrarily ordered and do not affect. So as long as the constraints on the letters that appear are consistent (i.e., no cycles), we can extend to a total order.

    But wait: There is a subtlety: The ancient alphabet had not more than 26 letters, and each letter is mapped to a distinct English alphabet. So the mapping is a bijection from the set of ancient letters to some subset of English letters (maybe all 26? Actually "mapped each letter to a different English alphabet", meaning each ancient letter corresponds to a distinct English letter. They typed all the words; so the letters appearing in the typed words are some subset of English letters, but those correspond to distinct ancient letters. However, there is no requirement that the mapping is onto all 26, but it's one-to-one from ancient to English. Since the ancient language has at most 26 letters, the mapping is injective into English letters. So any two distinct ancient letters map to distinct English letters. That means the English letters we see are distinct ancient letters, but there could be English letters that represent different ancient letters? Actually the mapping is from ancient letters to English letters. So each ancient letter gets a unique English letter. The words typed use those English letters. So if we see two different English letters, they correspond to two different ancient letters. So the mapping is already fixed: each English letter that appears represents a distinct ancient letter. But we are free to assign the ordering among these ancient letters. However, there is a catch: The English letters themselves have an inherent alphabetical order? No, we are allowed to consider any ordering of the alphabet, i.e., we can choose a permutation of the 26 letters to define the lex order. The typed words are just strings of symbols; we can assign any total order to the set of symbols (the 26 letters). So the fact that the mapping is to English letters is irrelevant; we just treat them as symbols.

    But there is one nuance: The ancient language might have fewer than 26 letters, but we have only used English letters, but there could be English letters not appearing. However, the ordering among those doesn't matter. So it's fine.

    Thus the problem reduces to: Given list of strings, check if there is a total order on the alphabet such that the sequence is lexicographically non-decreasing. This is equivalent to checking that:

    • No pair violates the prefix condition (i.e., a later word is a proper prefix of an earlier word).
    • The constraints of type c1 < c2 (from first differing character) are acyclic.

    But is that sufficient? Let's consider if there are cases where we need to also consider transitivity? The constraints themselves form a partial order; as long as there is no cycle, we can assign a linear extension. That seems straightforward.

    However, we must also consider that lexicographic order comparison also depends on later characters if earlier ones are equal. But we already capture the first differing character. So constraints are only on the first differing position. That's standard.

    But is there any other hidden condition? For instance, consider the scenario: words: ["ab", "ac", "cb"]. Constraints: from "ab" vs "ac": a=a, then b<c => b < c. From "ac" vs "cb": a vs c => a < c. So constraints: b < c, a < c. That's fine, we can have order a < b < c or b < a < c etc, as long as a < c and b < c. So possible. But is there a scenario where the constraints are acyclic, yet the ordering cannot be realized because of the prefix rule? For example, consider ["a", "ab", "b"]. Constraints: "a" vs "ab": prefix, no constraint. "ab" vs "b": first differ at position 1: a vs b => a < b. So constraints: a < b, fine. However, if we had ["ab", "a", "b"], then "ab" vs "a": "a" is a prefix of "ab"? Actually "a" is a prefix of "ab"? Yes, "a" is a prefix of "ab". But we have "ab" first then "a". Since "a" is a prefix of "ab", in lex order "a" < "ab". So "ab" > "a". This would violate non-decreasing order regardless of letter ordering. So immediate no. So prefix violations are captured.

    Now, what about the case where the same pair of letters gets both a < and > constraint? That would be a cycle of length 2, which we detect.

    Thus the algorithm: For each dataset, read n, then list of n strings. Then iterate i from 0 to n-2, compare word[i] and word[i+1].

    We need to determine if word[i] <= word[i+1] can be satisfied with some order.

    Comparison steps:

    • If word[i] == word[i+1]: continue (no constraint, but also they are equal, which is fine)
    • Else find the first position k where they differ, with k < len(word[i]) and k < len(word[i+1]).
      • If no such k because one is a prefix of the other: then if len(word[i]) > len(word[i+1]), then word[i] > word[i+1] inevitably, so answer no.
      • Else (len(word[i]) < len(word[i+1])): word[i] is prefix, so word[i] < word[i+1] automatically, continue.
    • Else: let c1 = word[i][k], c2 = word[i+1][k]. Add a constraint c1 < c2 (i.e., directed edge from c1 to c2).

    After building the graph (with vertices being letters a-z), check for cycles. If any cycle, answer no; else yes.

    But wait, there is an additional subtlety: The lexicographic order requires that if two words have same prefix, the comparison is determined by the first differing character. However, we also need to ensure that the order respects that if two strings are equal up to the end of one, the shorter is less. That's already handled.

    But is there a situation where the constraints we derive are necessary but not sufficient? Let's consider the classic problem of verifying if a given list is sorted according to some unknown ordering. Typically, we can derive constraints and then check consistency. That is indeed sufficient: If there exists a linear order satisfying all constraints, then we can define the lex order accordingly and the list will be sorted. But is there any case where the list might be sorted under some order but the constraints we derived from consecutive pairs are insufficient? For example, might we need to consider non-consecutive pairs? Actually if the list is sorted, then every consecutive pair must be non-decreasing. Conversely, if consecutive pairs are non-decreasing, then the whole list is non-decreasing by transitivity? Not exactly: In normal sorting, if each consecutive pair is in order, the whole sequence is sorted. That's because the order relation is transitive. So checking consecutive pairs is sufficient. Therefore, if we can assign an order such that each consecutive pair is in order, then the whole list is sorted.

    But there is a nuance: The lexicographic ordering depends on the global order of letters. If we satisfy all consecutive constraints, then by transitivity, for any i < j, word[i] <= word[j] will also hold? Not necessarily automatically. Suppose we have constraints a < b and b < c, then we can have order a<b<c, and then indeed word[i] <= word[j] for all i<j? Actually lexicographic ordering is not just based on the first differing character; if the first differing characters satisfy the order, then it's fine. But could it happen that the constraints are satisfied for each consecutive pair, but for some non-consecutive pair, the order would be violated under any linear extension that satisfies the constraints? If that happens, then there is no linear extension that makes all consecutive pairs non-decreasing? Let's think.

    We have a set of constraints from consecutive pairs: for each i, we have either no constraint or a constraint c1 < c2. If we can assign a total order on letters that satisfies all these constraints, then for each consecutive pair, the comparison will be correct: if prefix case, it's automatic; if differing, c1 < c2 ensures word[i] < word[i+1]; if equal, it's fine. So under that total order, the list is sorted. So the existence of such total order is exactly what we need.

    But the potential problem is that the constraints may be insufficient to guarantee that the list is sorted because there may be additional constraints that are implied by the transitivity of lexicographic order across non-consecutive pairs? Wait, those constraints are not directly imposed; they are consequences if the order is consistent. But if we satisfy the consecutive constraints, do we automatically satisfy that for any i < j, word[i] <= word[j]? Let's test with a counterexample. Suppose we have words: ["ba", "ab"] with just these two, consecutive pair is ba and ab. Comparing ba and ab: first character b vs a. For ba <= ab to hold, we need b < a. So constraint b < a. That's possible if we order b before a. So we can have order b < a, then ba < ab? Let's check: b < a, so ba vs ab: compare first char: b vs a; since b < a, ba < ab? Actually in lex order, if first char is smaller, the whole word is smaller. So ba < ab if b < a. So it's fine. So list ["ba", "ab"] is sorted under order b < a. That seems correct: under that order, "ba" comes before "ab". So yes.

    Now, consider three words: ["ba", "b", "ab"]. Consecutive pairs: "ba" vs "b": compare: first char both b, then "ba" has extra char, "b" ends. So "b" is prefix of "ba"? Actually "b" is a prefix of "ba"? Yes, "b" is a prefix of "ba". So in lex order, "b" < "ba". But here we have "ba" then "b", so we have "ba" > "b". That's a violation regardless of order. So it's no.

    What about ["ac", "ab", "aa"]? Compare "ac" vs "ab": first differ at second char: c vs b => need c < b. "ab" vs "aa": first differ at second char: b vs a => need b < a. So constraints: c < b and b < a => implies c < a. That's consistent (e.g., c<b<a). So there exists order c<b<a. Under that order, is the list sorted? Let's check: "ac" vs "ab": first char a = a, second: c vs b, since c<b, "ac" < "ab"? Actually if c<b, then "ac" < "ab"? Wait, lexicographic: compare first char: both a; then compare second: c vs b; if c<b, then "ac" > "ab" because the second character of "ac" is greater. Actually we need "ac" <= "ab". So we need c <= b. With c<b, we have c < b, so "ac" < "ab"? Let's be precise: If c<b, then c is less than b, so "ac" < "ab". Because at the first differing position, the character in "ac" is c, which is less than b, so "ac" < "ab". Good. So "ac" < "ab". Next, "ab" vs "aa": first char a=a, second b vs a: if b<a, then b is less than a? Actually b<a means b is less than a, so "ab" < "aa". So "ab" < "aa". So the sequence is "ac" < "ab" < "aa", so it's increasing? Actually "ac" < "ab" and "ab" < "aa", so "ac" < "ab" < "aa", so it's sorted ascending. So the list is sorted under c<b<a. So yes.

    Thus constraints from consecutive pairs suffice.

    But there is a subtlety: The constraints only involve letters that appear at the first differing positions. However, there could be implicit constraints due to the fact that the order must be a total order of all 26 letters? But that's fine.

    One more nuance: The mapping is from ancient letters to English letters, and the mapping is one-to-one. But does that impose that the ordering we assign must be a total order on all letters (including unused)? That's fine; we can extend arbitrarily.

    Now, the main difficulty: Are there any cases where the constraints are acyclic but still impossible due to the prefix rule interacting with the ordering? For example, consider words: ["a", "ab", "ac"]. That's fine. But what about ["ab", "a"]? That's prefix violation and we catch it.

    But what about a case where we have two words that are identical except one is longer and we have a constraint from other pairs that forces the opposite ordering? But prefix rule is absolute: if one is prefix of another, the shorter is always less. So if in the list we have a longer word before a shorter word that is a prefix, that's impossible regardless of order. So we check that.

    Thus the algorithm is clear.

    But wait, there is a twist: The problem statement says: "How the words are ordered in the dictionary, especially whether they are ordered lexicographically, is an interesting topic to many people. As a good programmer, you are requested to write a program to judge whether we can consider the words to be sorted in a lexicographical order."

    Maybe they want to know if the given list is sorted according to some permutation of the alphabet. That's exactly what we described.

    But I recall a known problem from ACM/ICPC called "Ancient Dictionary" or something similar? Possibly UVA 1100? I'm not sure. But it's essentially checking if a sequence can be lex sorted by some order.

    Double-check with examples provided:

    Input: 4 cba cab b a

    Output: yes

    Let's analyze: words: cba, cab, b, a. Compare cba vs cab: first differ at position 2? cba: c b a; cab: c a b. Actually index: 0: c == c; 1: b vs a, so b and a. So we need b < a? Wait to have cba <= cab, we need at first differing character: b (from cba) and a (from cab). So we need b < a. Add constraint b < a. cab vs b: first character c vs b, so need c < b. Add constraint c < b. b vs a: first character b vs a, so need b < a. Already have that. Constraints: c < b, b < a. So a cycle? No, it's a chain: c < b < a. So possible. So yes.

    Second dataset: 3 bca ab a

    Output: no.

    Check: bca vs ab: first char b vs a, need b < a. ab vs a: "a" is prefix of "ab"? Actually "a" is prefix of "ab"? No: ab vs a: compare: first char a = a? Wait, ab vs a: The first character of ab is a, second word a is single 'a'. They match up to the length of the shorter (1). Since they match all characters of the shorter, and the second word is shorter (length 1 vs 2), then the second word is a prefix of the first? Actually ab is longer, a is shorter. In lex order, the shorter word is less if it is a prefix. So here ab (longer) vs a (shorter): a is a prefix of ab, so ab > a. So for order to be non-decreasing, we need ab <= a. But ab > a always, impossible. So answer no. Good.

    Third dataset: 5 abc acb b c c

    Output: yes.

    Check: abc vs acb: first differ at 1: b vs c? Actually abc: a b c; acb: a c b; first differ at index 1: b vs c => b < c. acb vs b: first char a vs b => a < b. b vs c: first char b vs c => b < c. c vs c: equal. Constraints: b < c, a < b, b < c => a < b < c. No cycle. So yes.

    Fourth dataset: 5 abc acb c b b

    Output: no.

    Words: abc, acb, c, b, b. Constraints: abc vs acb: b < c (as before) acb vs c: first char a vs c => a < c c vs b: first char c vs b => c < b b vs b: equal. Now we have b < c, a < c, c < b => combining: b < c and c < b => cycle b < c < b. So impossible. So no.

    Matches output.

    So the approach is correct.

    Now the challenge: Implementation details. Input contains multiple datasets ending with 0. n up to 500, strings up to 10 characters. So number of datasets maybe several. So we can build a graph of 26 nodes. Use adjacency list or matrix. Detect cycles using topological sort or DFS.

    We need to be careful: There might be duplicate constraints; we can ignore duplicates.

    But also, there may be constraints that lead to contradictions like a < a? That would be if we have a string compared to another where they differ but the characters are same? That can't happen because they differ. So no self loops.

    Edge case: If we have constraint a < b and also b < a from different pairs? That yields a cycle. So detection of cycle via topological sort or DFS.

    But we must also consider if there is any scenario where a word is a prefix of the next, but later constraints force something that contradicts the prefix rule? That can't happen because the prefix rule is independent of letter order. So we just check that.

    One more nuance: The list may contain identical words. That's fine.

    So algorithm:

    For each dataset:

    • Read n.
    • If n==0 break.
    • Read n strings.
    • Initialize graph: set of vertices = set of letters that appear? But we can represent graph for all 26 letters, but only edges among some.
    • Also we can keep a set of constraints as edges.
    • Also an array indegree for topological sort.

    But we also need to consider that constraints might be redundant.

    Now, detection of cycles: we can perform topological sort on the directed graph. If we can order all letters involved such that edges go from earlier to later, it's consistent. We don't need to order all letters, just those that appear in constraints. But we need to include all letters? Actually letters that don't appear have no constraints, they can be placed anywhere. So cycle detection only on the graph formed by constraints.

    We can do:

    • Create adjacency list: vector<vector> graph(26).
    • vector indegree(26,0).
    • set letters (maybe not needed)
    • For each pair (i,i+1): find first differing position. If one is prefix of other: if len(prev) > len(next): output no (immediate failure). else continue. Else: let u = prev[k], v = next[k]; if u != v: add edge from u to v (if not already added to avoid duplicate indegree increments). But since n <= 500, duplicates are few; we can use a set of pair to avoid duplicates. Or we can just add and increment indegree each time, but that would cause multiple edges leading to higher indegree counts but topological sort still works if we treat indegree as number of incoming edges (including duplicates). However, duplicate edges could cause indegree to be >1 for same source, but that's okay; they just represent same constraint. But when we process, we might reduce indegree multiple times if we treat each edge separately. But if we add duplicate edges, we might have extra indegree counts, making it impossible to reduce to zero? Actually, suppose we have two identical edges u->v. Then indegree[v] will be incremented twice. When we process u, we will for each outgoing edge decrement indegree of neighbor. If we have two edges, we will decrement twice. That's fine, but we need to store adjacency list with duplicates? If we store adjacency list with duplicates, we will process each edge. That's okay but may lead to inefficiency. However, it's simpler to just use a 26x26 boolean matrix to track if edge already added, and only add once. Since constraints are at most 500, it's fine.

    Simplify: use a set of pair<char,char> to store edges, then after processing all pairs, build graph with unique edges.

    Or we can do: for each new constraint, if not seen[u][v], add edge and indegree[v]++. Then proceed.

    Now, cycle detection: Use Kahn's algorithm: queue of nodes with indegree 0. Process all nodes (only those that appear? But we might have nodes that have no edges and not appear? That's fine, they have indegree 0, we can include them or just ignore. Actually for cycle detection, we need to check that there is no cycle among nodes that have edges. So we can do: collect set of letters involved in constraints (either as source or target). Also, letters that appear in words but not in constraints are isolated; they don't affect. So we can process only those letters that appear in constraints, but we must also consider that some letters might have indegree 0 but no outgoing edges; they are fine. In Kahn's, we can push all letters (a-z) with indegree 0 and present in letters set? Actually we need to ensure we can topologically sort the entire graph. But if we only consider nodes that appear in constraints, we need to count indegree only for them. But we also might have nodes that appear only as source or target; we should include them. So we can create a boolean array exists[26] to mark any letter that appears in any word or in any constraint. Actually constraints involve letters from words, so if a letter appears in a word, it may not be in constraints but that's okay. For topological sort, we only need to consider nodes that have edges. But nodes without edges are irrelevant to cycles. However, we must include them because they don't affect cycle detection. So we can just run Kahn's on all 26 letters, but we need to ensure we only process nodes that actually exist? Actually Kahn's algorithm works on all nodes; if a node has no indegree and no outgoing edges, it's fine. But we need to know which nodes are actually present? We don't need to restrict; we can run on all 26 letters. But indegree array will be zero for letters not in any edge. They will be popped and processed. That's okay. However, we need to have adjacency list for them (empty). So we can push all letters with indegree 0 initially? But then we would push all 26 letters if none have indegree >0? That's okay but we want to detect cycles. In Kahn's algorithm, after processing, if we have processed all nodes (i.e., count of nodes visited equals number of nodes in the graph), then no cycle. If we consider all 26 letters, then we must process all 26. But if some letters have no edges and we still include them, we will process them and count will be 26. That's fine. However, if there is a cycle among some letters, indegree for nodes in cycle will never become 0, so we won't process all 26, and we'll detect cycle.

    But there's a subtlety: Some letters may not appear at all in the dictionary, and also not in constraints. They have indegree 0. We would still include them in the set of nodes to process. That's okay; we will pop them, but we need to have adjacency list entries for them. That's fine.

    But a potential issue: If we include all 26 letters, and there is a cycle among some letters, we will still have some nodes with indegree >0. Kahn's algorithm will pop only nodes with indegree 0; eventually queue empties before processing all 26. Then we detect cycle. So it's okay.

    Thus we can simply use all 26 letters. But careful: For letters that appear in constraints but also have self-loop? That can't happen because constraints are u<v with u!=v. So no self-loops.

    Implementation:

    For each dataset:

    • read n.

    • if n==0 break.

    • vector words(n)

    • for i: read words[i]

    • bool possible = true;

    • bool edges[26][26] = {false};

    • int indegree[26] = {0};

    • for i from 0 to n-2: string &a = words[i], &b = words[i+1]; // compare size_t minlen = min(a.size(), b.size()); int diffpos = -1; for j=0; j<minlen; j++) { if (a[j] != b[j]) { diffpos = j; break; } } if (diffpos == -1) { // one is prefix of the other if (a.size() > b.size()) { possible = false; break; } // else a.size() <= b.size() => a is prefix, ok } else { char u = a[diffpos], v = b[diffpos]; // add constraint u < v if (u != v) { // only if edge not already added if (!edges[u-'a'][v-'a']) { edges[u-'a'][v-'a'] = true; graph[u-'a'].push_back(v-'a'); // if we maintain adjacency list indegree[v-'a']++; } } }

    • if (!possible) { print "no"; continue; }

    • Now detect cycle via Kahn's: queue q; for (int i=0; i<26; i++) { if (indegree[i] == 0) q.push(i); } int processed = 0; while (!q.empty()) { int u = q.front(); q.pop(); processed++; for (int v : graph[u]) { indegree[v]--; if (indegree[v] == 0) q.push(v); } } if (processed == 26) print "yes" else print "no"

    But is processing all 26 always correct? Consider a scenario where there are no constraints at all (e.g., all words are prefixes or identical). Then indegree all zero, processed=26 => yes. That's correct.

    Now, what about scenario where there is a constraint that involves a letter that never appears? That can't happen because constraints come from letters in words.

    But note: When we add edges, we need to ensure we have an adjacency list. We can use vector<vector> graph(26). Clear it per dataset.

    Potential pitfall: If we have a constraint u<v, but also later we have v<u (from another pair), we add both edges, causing a cycle. Kahn's will detect because processed < 26.

    Now, about prefix check: If we have a situation where a is prefix of b, but they are equal length? Then they are equal, not prefix. So we handle equality earlier: if diffpos == -1 and lengths equal, then words are equal, no prefix issue, continue (possible). If diffpos == -1 and len(a) > len(b), it's impossible. So we break.

    Thus algorithm done.

    But wait, is there any scenario where the constraints are acyclic but still impossible because of the prefix rule combined with the order of letters? Suppose we have words: ["ab", "ac", "b"]. Check: "ab" vs "ac": b<c => b<c. "ac" vs "b": a vs b => a<b. So constraints: b<c, a<b. That's a<b<c. Then check if any prefix violation? "ab" is not prefix of "ac", "ac" vs "b": not prefix, fine. So order a<b<c yields: ab < ac? Compare: a=a, b<c => ab<ac, good. ac vs b: a<b => ac<b, so ac < b, thus list is ascending: ab < ac < b. So yes.

    Now consider ["b", "ab", "a"]. "b" vs "ab": first char b vs a => need b < a. "ab" vs "a": "a" is prefix of "ab"? Actually "a" is prefix of "ab", so ab > a automatically. So we have b < a constraint, but also ab > a, so the sequence is b, ab, a. For it to be sorted, we need b <= ab and ab <= a. b <= ab can be satisfied if b < a? Wait b vs ab: compare first char b vs a, if b < a then b < ab? Actually if b < a, then b > a? Let's see: if b < a, then b is less than a. In lex order, comparing "b" and "ab": first char b vs a, since b < a? Actually if b is less than a, then b < a? No, less means earlier. If b < a, then b comes before a. So "b" would be less than "ab"? Because first character: b vs a; if b < a, then "b" < "ab". So b < ab. That is okay. Next ab vs a: a is prefix, so ab > a. So we have b < ab and ab > a, so b < ab > a. For sorted order we need b <= ab <= a, but ab > a, so fails regardless. So it's impossible because of the prefix violation (ab > a). So we catch that.

    Now, what about more complex interactions where the ordering might affect whether a word is considered a prefix? No, prefix is purely length and equality of characters, independent of order. So fine.

    Thus the solution is straightforward.

    But before concluding, we should test some edge cases:

    • n=1: always yes because no pair constraints.

    • Strings may be empty? The problem says each string consists of up to 10 English lowercase letters. It doesn't say they are non-empty, but "up to 10" suggests possibly empty? Usually these problems assume at least one letter? But "up to 10" might include zero? Typically they say "up to 10" meaning maximum length 10, but could be zero? I'd assume at least 1, because they are words. But to be safe, we should consider empty strings. An empty string is a prefix of any string. In lexicographic order, empty string precedes any non-empty string. So if we have an empty string, it should be first. So our prefix check: If we have an empty string and a non-empty string, empty is prefix. So if we have a non-empty then empty later, that's invalid. Our code: For strings, size() can be zero. The comparison loop: minlen = min(a.size(), b.size()) = 0, diffpos remains -1. Then if a.size() > b.size() then invalid. So if a is non-empty and b is empty, a.size()>0, b.size()==0 => a.size() > b.size(), so invalid. If a is empty and b is non-empty, it's valid. So works.

    • Strings with uppercase? Only lowercase.

    • Duplicate constraints: we already handle with seen matrix.

    Now, the algorithm complexity: For each dataset, O(n * L) for comparisons, where L ≤ 10, and building graph with at most 26 nodes, and topological sort O(26+edges) trivial.

    Now, we need to be careful about the ordering of letters: The custom order is a total order on the 26 letters. But what if there are letters that appear only in the dictionary but no constraints? They can be placed anywhere, so consistent.

    Now, are there any scenarios where the constraints are acyclic, but the order we assign might cause a word to be equal to another word? Equality is determined by characters being identical; the ordering doesn't affect equality. So if two words are not identical, they won't become equal under any order. So no issue.

    One more nuance: The problem says "we can consider the words to be ordered lexicographically." That means we ask: Is there some permutation of the alphabet (i.e., some total order) such that the given list is sorted in non-decreasing order? That's what we do.

    But is there any requirement that the order must be consistent across all datasets? No, each dataset independent.

    Thus the solution is as above.

    But wait, is there a possibility that the list is sorted according to the custom order, but the constraints we derive from consecutive pairs are not sufficient to guarantee that the custom order can be extended to a total order? Actually we are constructing constraints exactly necessary for the list to be sorted. If there exists a total order, then those constraints must hold (since for each consecutive pair, the relation must hold, which yields those inequalities). Conversely, if we can find a total order satisfying those constraints, then the list will be sorted? Let's verify carefully.

    Suppose we have constraints C = {u_i < v_i} from consecutive pairs. If we assign a total order that respects all these constraints, then for each consecutive pair, the lexicographic comparison will yield the correct inequality? Not necessarily: consider a case where the two words have a differing character, and we have u < v. Under a total order where u < v, we get that the first word is less than the second? Let's formalize: For words A and B, let k be first index where they differ. Then A[k] = u, B[k] = v. If u < v in the custom order, then A < B. If u > v, then A > B. If u = v, they wouldn't differ. So the constraint u < v ensures A < B. So good.

    Now, what about the case where A is a prefix of B? Then regardless of order, A < B. So no constraint needed.

    Now, what about case where they are identical? Then A = B, no constraint.

    Thus the constraints are both necessary and sufficient for each consecutive pair to be in order (given the order). So if we can satisfy all constraints simultaneously with a total order, then each consecutive pair is in order, so the list is sorted.

    But is it possible that satisfying the constraints as a partial order is not enough to guarantee existence of a total order? Well, a partial order can always be extended to a total order if it is acyclic (i.e., a DAG). Actually a partial order defined by a DAG can be extended to a total order via topological sort. However, we must ensure that the constraints are indeed a partial order: they are relations of the form u < v. The transitive closure yields a partial order if there are no cycles. So yes, acyclic => there exists a total order that respects all constraints (linear extension). So cycle detection is sufficient.

    Thus algorithm stands.

    Now, potential pitfalls: What about constraints that involve letters that never appear? They come from words, so they appear. So fine.

    Now, we should test with a tricky case: Suppose we have words: ["ab", "ac", "cb"]. Constraints: "ab" vs "ac": b<c. "ac" vs "cb": a<c. So we have b<c and a<c. That's acyclic. Under an order where a < b < c, we have "ab" < "ac" and "ac" < "cb"? Check "ac" vs "cb": a vs c, a<c => "ac" < "cb". So sorted. Under order b<a<c also works: "ab" vs "ac": b<c (since c is same) still works; "ac" vs "cb": a vs c, a<c holds? Under b<a<c, a<c true. So works.

    But what about ["ab", "ba"]? Constraints: a < b? Actually "ab" vs "ba": first char a vs b => a < b. So constraint a < b. That's consistent. So we can have order a<b. Then "ab" < "ba". So sorted.

    Now, consider ["ba", "ab"] gives constraint b < a, which is also consistent if we set b<a. So both orders possible. So it's symmetric.

    Now, consider scenario where we have constraint a < b and also a < b from multiple pairs, fine.

    Now, about prefix: If we have ["ab", "abc", "ab"]? That is "ab", "abc", "ab". Check: "ab" vs "abc": prefix, ok. "abc" vs "ab": "ab" is prefix of "abc"? Actually "ab" is prefix of "abc", so "abc" > "ab". So this violates non-decreasing because we have "abc" then "ab". So answer no. Good.

    Now, what about ["a", "ab", "abc", "abcd"]: all prefixes, fine.

    Now, consider ["abc", "ab"]: "ab" is prefix of "abc", so "abc" > "ab", so not sorted. So no.

    Thus prefix check covers that.

    Now, we must also consider the possibility that the words themselves might not be valid under the mapping? For instance, the mapping is one-to-one from ancient letters to English letters. That implies that each English letter corresponds to a distinct ancient letter. But does that impose any constraint that the order must be a permutation? No.

    But wait: The mapping is fixed but unknown. So the words we see are strings of English letters. The actual lex order of the ancient language is some order on ancient letters. We are allowed to map those ancient letters to English letters arbitrarily (since the mapping is already done, but we can reinterpret the order). Actually, the scenario: We have the dictionary typed with English letters, each representing a distinct ancient letter. But we don't know which ancient letter corresponds to which English letter. The question: "whether we can consider the words to be sorted in a lexicographical order." That means: Is there a way to assign an ordering to the ancient letters (which correspond to the English letters) such that the typed words are sorted? Since the mapping from ancient to English is fixed but unknown, we can effectively choose an ordering for the English letters that reflects the order of the ancient letters. So it's exactly what we did.

    But is there any extra constraint: The mapping from ancient letters to English letters is one-to-one, but we don't know which English letter maps to which ancient letter. However, the typed words are given using English letters. If two words contain the same English letter, that means the same ancient letter appears in both. So the identity of letters is preserved across words. So we treat each English letter as a symbol for an ancient letter. So that's consistent.

    Thus no extra constraints.

    Now, implementation details: We'll need to read lines, maybe there are spaces? The strings are each on a line, no spaces. Use std::getline after reading n, but careful about newline. Simpler: use cin >> n then for i read string via cin >> s. That works.

    Now, potential pitfalls: The input ends with 0. So we read n, if n==0 break.

    Now, confirm with given examples.

    We'll implement solve() reading from standard input and writing to standard output.

    Now, I'll consider if there is any scenario where constraints could be contradictory even if acyclic? No, acyclic is sufficient.

    But wait, what about case where we have a constraint that a < a? That can't happen.

    Now, let's double-check with more complex constraints: Suppose we have words: ["ab", "ac", "ad", "ae"] all with same prefix 'a' and different second letters. Then we get constraints among the second letters: from "ab" vs "ac": b < c; "ac" vs "ad": c < d; "ad" vs "ae": d < e. That's a chain b<c<d<e. That's fine.

    Now, what about ["ab", "ac", "aa"]? "ab" vs "ac": b < c; "ac" vs "aa": c vs a at second char => c < a. So constraints b < c and c < a, which implies b < a as well. That's acyclic? b<c, c<a => b<a. So total order could be b < c < a? But c < a is there, so we need c < a, and b < c. So b < c < a works. Check: "ab" vs "ac": b < c => ab < ac. "ac" vs "aa": first char a=a, second c vs a; with c<a, ac > aa? Wait, if c<a, then c is greater than a or less? c<a means c is less than a. So if c < a, then ac < aa? Let's compute: compare "ac" and "aa": at first char both a; second char c vs a. If c < a, then c is smaller, so "ac" < "aa". That would make the sequence: "ab" < "ac" < "aa", which is sorted ascending. So yes it's fine.

    Now, if we had ["aa", "ab", "ac"]: constraints: a=a first char, second: a<b => a<b; "ab" vs "ac": b<c. So constraints a<b, b<c => a<b<c. That's fine.

    Now, if we had ["ac", "ab", "aa"]: we already saw constraints c<b and b<a => c<b<a. Works.

    Thus algorithm holds.

    Now, I'll consider potential nuance: The problem says "Note: In a lexicographical order, a word always precedes other words it is a prefix of. For example, ab precedes abc, abde, and so on." This is a reminder of the standard lexicographic ordering. However, some definitions of lexicographic ordering sometimes treat shorter strings as smaller only if they are prefix? Yes, that's standard. So we included.

    Now, could there be a scenario where the constraints are acyclic but the list still cannot be sorted because of the way ties are resolved with prefixes? Example: Suppose we have words: ["a", "ab", "ac", "abc"]. Consider the order: "a", "ab", "ac", "abc". Under any custom order, will "ab" < "ac"? That depends on b<c. If we set b>c, then "ab" > "ac". So we have constraint b<c from "ab" vs "ac". Also "ac" vs "abc": "ac" is not a prefix of "abc"? Actually "ac" and "abc": compare first char a=a, second char c vs b. So we need c < b? Wait, "ac" vs "abc": a vs a, then c vs b. For "ac" <= "abc", we need c <= b. Since they are different, we need c < b. But from earlier we have b < c. So conflict. But let's check: In this list, do we have "ac" then "abc"? That's the order: "a", "ab", "ac", "abc". For it to be sorted, we need "ac" <= "abc". At first difference: c vs b, so need c < b. But also from "ab" <= "ac", we need b < c. So we have both b<c and c<b => cycle. So it's not acyclic, we detect. So it's fine.

    But what if we had a different ordering like ["a", "ab", "abc", "ac"]? Check: "ab" vs "abc": prefix, okay; "abc" vs "ac": compare at second char: b vs c? Actually "abc" vs "ac": compare first a=a, second b vs c => need b < c. So constraint b<c. Also "ab" vs "ac": b<c again. So only b<c. That's consistent. So list sorted if b<c.

    Thus our approach handles.

    Now, what about the scenario where there are multiple constraints that don't directly conflict but impose an ordering that makes some later comparison invalid? But we already capture all consecutive constraints; if they are satisfied, the list is sorted. So no.

    Thus solution is simple.

    But wait, is there a case where we need to consider constraints beyond consecutive pairs to detect impossibility? For instance, consider words: ["ab", "bc", "ca"]. Constraints: "ab" vs "bc": a<b? Actually first char a vs b => a<b. "bc" vs "ca": b vs c => b<c. So constraints a<b, b<c. That's acyclic. So we would say yes. But is there a total order that makes this list sorted? Let's test with order a<b<c. Then "ab" < "bc"? Compare a vs b: a<b => "ab" < "bc". "bc" < "ca"? Compare b vs c: b<c => "bc" < "ca". So yes. So it's valid.

    Now consider ["ac", "cb", "ba"]. Constraints: "ac" vs "cb": a<c. "cb" vs "ba": c vs b => c<b. So a<c and c<b => implies a<b. That's acyclic (a<c<b). Check: order a<c<b. Then "ac" < "cb"? Compare a vs c: a<c => "ac" < "cb". "cb" < "ba"? Compare c vs b: c<b => "cb" < "ba". So yes.

    Now consider ["ac", "ab", "aa"]. Already did, works with c<b<a.

    Now, could there be a case where constraints are acyclic but the actual lex order fails because of some transitive relationship that is not captured? For instance, suppose we have three words A, B, C. If A <= B and B <= C hold, does A <= C automatically hold for lex order under any total order? Not necessarily. In fact, lex order is transitive: if A <= B and B <= C, then A <= C for any total order? Let's verify: Lex order is a total order on strings given a total order on characters? Actually lex order based on a total order on characters is a total order on strings? It is a total order if we consider strings of finite length? Typically, lexicographic order with a total order on alphabet is a total order if we also define that a shorter string that is a prefix is less than longer. This order is indeed a total order (assuming we have a well-order). Actually, it's a linear order: It is antisymmetric, transitive, and total. Because given any two strings, you can compare them. And the comparison respects transitivity. So if we have A <= B and B <= C, then A <= C must hold by the properties of total order. But is that always true given the same underlying total order on characters? Yes, because it's a total order on strings. So if we find a total order on characters that makes A <= B and B <= C, then automatically A <= C. So we don't need to check non-consecutive pairs.

    But what if we have a total order on characters that satisfies the constraints from consecutive pairs but does not satisfy the transitivity of lex order? That can't happen; lex order is defined based on that character order. Once you have a character order, the lex order on strings is fully defined and is a total order. So if consecutive pairs are ordered, the whole list is ordered.

    Thus solution is sound.

    Now, we should implement.

    One more nuance: The strings can be up to 10 characters, but there can be up to 500 strings, so we can compare directly.

    Now, about cycle detection: Since we have only 26 nodes, we could also use Floyd-Warshall or DFS to detect cycles. But Kahn's is simple.

    Implementation steps:

    • While (true):
      • Read n (int)
      • if n == 0: break
      • vector words(n)
      • for i=0..n-1: cin >> words[i]
      • bool ok = true
      • vector<vector> graph(26)
      • int indeg[26] = {0}
      • bool edge[26][26] = {false}
      • for i=0..n-2: string &a = words[i], &b = words[i+1]; // find first mismatch size_t len = min(a.length(), b.length()); int diff = -1; for (size_t j=0; j<len; j++) { if (a[j] != b[j]) { diff = j; break; } } if (diff == -1) { // all equal up to min len if (a.length() > b.length()) { ok = false; break; } // else a.length() <= b.length() => fine } else { char u = a[diff], v = b[diff]; if (u != v) { int ui = u-'a', vi = v-'a'; if (!edge[ui][vi]) { edge[ui][vi] = true; graph[ui].push_back(vi); indeg[vi]++; } } }
      • if (!ok) { cout << "no\n"; continue; }
      • // topological sort
      • queue q;
      • for (int i=0; i<26; i++) if (indeg[i]==0) q.push(i);
      • int cnt = 0;
      • while (!q.empty()) { int u = q.front(); q.pop(); cnt++; for (int v : graph[u]) { indeg[v]--; if (indeg[v]==0) q.push(v); } }
      • if (cnt == 26) cout << "yes\n"; else cout << "no\n";

    But note: There's a subtle point: When we have duplicate constraints, we ignore duplicates. But what if there is a constraint u<v and also v<u from other pairs? We add both edges, creating a cycle. In Kahn's algorithm, we will not process both nodes? Actually if we add both edges, indegree of both will be at least 1. For a 2-cycle, both nodes have indegree 1 (u has edge from v, v from u). Neither will become 0 initially, so they won't be enqueued. So processed nodes will be less than 26, so we detect cycle. That's fine. So we can also add duplicate edges without checking, but then indegree counts could be >1 for same edge. If we have u<v from two different pairs, we add edge twice. That would make indegree[v] incremented twice. When we process u, we will decrement indegree[v] twice (once for each edge) if we have both edges in adjacency list. That's fine as long as we have both entries. However, it could lead to extra processing but no harm. But we must be careful: If we add duplicate edges, indegree[v] becomes 2, but when we process u once, we will iterate over both duplicate edges and decrement twice, resulting in indegree[v] = 0 after both decrements. That's okay. But what if there is a cycle of length 2 with duplicate edges? For u and v, we might have edges u->v (multiple) and v->u (multiple). indegree[u] = number of v->u edges, indegree[v] = number of u->v edges. Initially, both >0, so neither enqueued. So cycle detection works. However, if we have duplicate edges and later after processing other nodes we might reduce indegree? No, because u and v are only sources if indegree becomes 0, but they won't become 0 because they have incoming edges from each other. So still cycle.

    But if we add duplicates, we might have extra edges that increase indegree, but still the algorithm works. However, it might cause a situation where we miss a node being processed because indegree is >0 due to duplicates? That's fine. The only potential issue is if there is a self-loop? That won't happen.

    But we must be careful: When we add duplicate edges, we need to have them in adjacency list to decrement indegree appropriately. If we only increment indegree without adding adjacency list entries (or if we only add one adjacency but indegree reflects multiple), then when we process the source, we would decrement indegree only once, leaving indegree >0 and never reaching 0. That would cause a false cycle detection. So we must either:

    • Use a set to avoid duplicates and add edge once, indegree = 1 if edge exists.
    • Or, if we add duplicates, we need to add each edge to adjacency list separately and increment indegree each time. Then when we process the source, we iterate over all outgoing edges (including duplicates) and decrement indegree for each. That works.

    Simpler: Use a boolean matrix to track if edge already added. Then add only once. I'll do that.

    Now, we also need to consider the case where there are letters that never appear but have no constraints. In topological sort we push all 26 letters with indegree 0. That's fine. But note: If we have only some letters appearing, they might have edges. However, if there is a cycle among some letters, processed count will be less than 26. But what if we have a letter that appears but has no constraints and no edges? It will have indegree 0 and will be enqueued. That's fine.

    Now, could there be a situation where the constraints are consistent but the graph is not a DAG because of a cycle among letters that are not used? Not possible.

    Thus the solution is correct.

    But wait, there is a nuance: In lexicographic order, if two strings are identical, they are equal. Our code treats them as equal, no constraint. That's correct.

    Now, we must also consider the possibility of multiple constraints that lead to a partial order that can't be extended? That's exactly cycles.

    Now, let's reflect on potential pitfalls: What about the case where we have a string that is a prefix of the next but also we have a constraint from other parts that forces the opposite? For example, consider words: ["ab", "a", "b"]. "ab" vs "a": "a" is prefix of "ab"? Actually "a" is prefix of "ab". So "ab" > "a". So immediate failure. So we would catch it.

    Now, what about words that are not in order because of prefix but if we reorder the letters we could make the longer one smaller? For example, can "ab" be less than "a" under some order? No, because when comparing "ab" and "a", we compare characters: 'a' equals 'a', then we reach end of "a", so "a" is considered shorter. According to lexicographic rules, the shorter string is considered smaller if it is a prefix. So "ab" > "a" always. So indeed, any order cannot change that.

    Thus, we have a complete solution.

    Now, let's think about the time constraints: Up to 500 words per dataset, and number of datasets unspecified but probably not huge. Our algorithm is O(n * L + 26^2) per dataset, which is fine.

    Edge Cases:

    • n=0 is termination, not a dataset.
    • Strings may be up to 10 length, but can be same length or different.
    • Letters are only lowercase English.

    Now, let's consider if there is any scenario where we have to consider not just the first differing character but also later characters because of equality? No.

    Now, verify with sample.

    Now, think about possibility of duplicate words: e.g., ["a","a","a"] => all equal, no constraints, no prefix violation, answer yes.

    Now, what about ["ba","ab","a"]? Check: "ba" vs "ab": first char b vs a => b < a? Actually need ba <= ab: so need b < a. Add constraint b < a. "ab" vs "a": "a" is prefix of "ab"? "a" is prefix of "ab". So ab > a, which violates order because we need ab <= a. So answer no. That's correct.

    Now, what about ["a","b","ab"]? "a" vs "b": a<b => constraint a<b. "b" vs "ab": first char b vs a => need b < a. So we have a<b and b<a -> cycle. So no. Indeed, cannot have a<b and b<a. So answer no.

    Now, if we have ["a","ab","b"]: "a" vs "ab": prefix, ok; "ab" vs "b": first char a vs b => need a<b. So only a<b, that's fine. So yes.

    Now, check: "a" < "ab" because prefix; "ab" < "b" if a<b. So list sorted if a<b. Yes.

    Now, what about ["a","b","ab"]? As above, cycle.

    Thus algorithm works.

    Now, final step: Implementation in C++.

    We'll write a solve() function.

    Pseudo-code:

    #include #include #include #include #include using namespace std;

    int main() { int n; while (cin >> n, n != 0) { vector words(n); for (int i = 0; i < n; ++i) cin >> words[i]; bool possible = true; vector<vector> graph(26); int indeg[26] = {0}; bool edge[26][26] = {false}; for (int i = 0; i < n-1; ++i) { const string &a = words[i], &b = words[i+1]; // compare size_t minlen = min(a.size(), b.size()); size_t j = 0; while (j < minlen && a[j] == b[j]) ++j; if (j == minlen) { // one is prefix if (a.size() > b.size()) { possible = false; break; } // else fine } else { char u = a[j], v = b[j]; int ui = u - 'a', vi = v - 'a'; if (!edge[ui][vi]) { edge[ui][vi] = true; graph[ui].push_back(vi); indeg[vi]++; } } } if (!possible) { cout << "no" << endl; continue; } // topological sort queue q; for (int i = 0; i < 26; ++i) { if (indeg[i] == 0) q.push(i); } int processed = 0; while (!q.empty()) { int u = q.front(); q.pop(); processed++; for (int v : graph[u]) { if (--indeg[v] == 0) { q.push(v); } } } if (processed == 26) cout << "yes" << endl; else cout << "no" << endl; } return 0; }

    But careful: In the topological sort, after we decrement indeg[v], we should check if it becomes zero. That's fine.

    Now, consider potential subtlety: The graph may have nodes that are not reachable from any source, but if they have indegree >0 they are part of a cycle. If a node has indegree >0 but no outgoing edges, but it's part of a cycle? Actually if it has indegree >0 and no outgoing edges, it could be a sink with incoming edges; but that's fine if those incoming edges come from nodes that can be processed. For topological sort to succeed, we need to process all nodes. If a node has indegree >0 initially, it will be processed when its indegree becomes zero. So our algorithm works.

    Now, test with sample.

    Now, I want to double-check if we need to consider any scenario where the order of letters might need to be consistent with the prefix rule in a more subtle way. For example, consider words: ["a", "b", "aa"]. Let's test: "a" vs "b": a<b? need a<b. "b" vs "aa": first char b vs a => need b < a. So constraints a<b and b<a -> cycle. So no. Is there any order that could make this list sorted? Let's see: we need a < b (from first) and also b < a (from second) impossible. So no.

    What about ["a", "aa", "b"]? "a" vs "aa": prefix -> ok. "aa" vs "b": first char a vs b => a<b. So only a<b. So sorted if a<b. Also check: a < aa < b. Under a<b, is aa < b? Yes, because a<b, so aa < b. So yes.

    Now, what about ["aa", "ab", "b"]? "aa" vs "ab": a=a, second a vs b => a<b. "ab" vs "b": a vs b => a<b. So only a<b. So sorted if a<b: aa < ab < b? Check ab vs b: a<b, so ab < b. Yes.

    Now, what about ["b", "aa", "ab"]? This order: "b", "aa", "ab". Compare "b" vs "aa": b vs a => need b < a. "aa" vs "ab": a=a, second a vs b => a<b. So constraints b<a and a<b => cycle. So no.

    Thus our approach works.

    Now, could there be a case where constraints are acyclic but the list is not sorted because of prefix rule that is not captured by consecutive pairs? For example, consider words: ["ab", "c", "abc"]. Wait, check: "ab" vs "c": first char a vs c => a<c. "c" vs "abc": first char c vs a => c<a. So we get a<c and c<a -> cycle. So no.

    Now, consider ["ab", "abc", "ac"]? "ab" vs "abc": prefix -> ok. "abc" vs "ac": first differ at second char: b vs c => b<c. So constraint b<c. That's acyclic. But does that ordering produce sorted list? Under order b<c, we have: ab < abc (prefix) and abc < ac? Compare abc vs ac: a=a, b vs c: if b<c, then abc < ac. So sorted. So yes.

    Now, think about a tricky case: Suppose we have words: ["ab", "ac", "ad", "abc"]? Let's test: "ab" vs "ac": b<c. "ac" vs "ad": c<d. "ad" vs "abc": compare a=a, then d vs b? Actually "ad" vs "abc": first char a