

2. Write a C++ program (or Java) for hw10_2 that displays the alphabetical order of characters for an alien language. Input format: This is a sample input from a user. a 3 caa aaa aab The first line (= 3 in the example) indicates that there are three words in the following lines which are "caa", "aaa", and "aab”. Note that the three words presented in the input are "sorted” order in the alien language. As you can see, the sorted sequence of words is different from our English. For the program, you should remember that the alphabetical order of characters in the alien language is different from our English. Your program should determine the correct order of characters of the language. For the homework, you can assume the alien alphabet consists of 26 or fewer characters from a to z. Sample Run 0: Assume that the user typed the following lines 3 ??? aaa aab
This is the correct output. Since the word "caa" comes before "aaa" and "aab", you know that the character 'c' should come before the character 'a'. Similarly, you know that the character 'a' precedes 'b' based on the sequence "aaa" and "aab”. C->a->b Sample Run 1: Assume that the user typed the following lines 9 ??? eeb eef aaa aab deed deeb def daad come From the input, you know that 'c' sho the chai 'e'. Similarly, you know the following relationships among the letters: "c' + 'a', 'c' ? d', 'e' + 'a', 'e' + 'd', 'b' + 'f', 'a' ? 'd', 'a' ? b', 'd' = 'b', 'e' ? ‘f”. Based on the relationships, this is the correct output. For the homework, you can assume the input is always valid. In other words, you will have the correct order for the input. C->e->a->d->b->f Sample Run 2: Assume that the user typed the following lines. From the input, you know the following relationships among the letters: 'a' + 'b', 'a' ? d', 'a' + 'c','b' ? 'd', 'b' + 'c','d' + 'c'. 5 a ab bba ddd cca ccc This is the correct output. a->b->d->c Hint: Construct a direct graph using all characters in the words. Then, use a topological sorting to identify the sequence of the characters.