Problem A
Cantina of Babel
Characters in Star Wars each speak a language, but they typically understand a lot more languages that they don’t or can’t speak. For example, Han Solo might speak in Galactic Basic and Chewbacca might respond in Shyriiwook; since they each understand the language spoken by the other, they can communicate just fine like this.
We’ll say two characters can converse if they can exchange messages in both directions. Even if they didn’t understand each other’s languages, two characters can still converse as long as there is a sequence of characters who could translate for them through a sequence of intermediate languages. For example, Jabba the Hutt and R2D2 might be able to converse with some help. Maybe when Jabba spoke in Huttese, Boba Fett could translate to Basic, which R2D2 understands. When R2D2 replies in Binary, maybe Luke could translate to Basic and then Bib Fortuna could translate back to Huttese for Jabba.
In Star Wars Episode IV, there’s a scene with a lot of
different characters in a cantina, all speaking different
languages. Some pairs of characters may not be able to converse
(even if others in the cantina are willing to serve as
translators). This can lead to all kinds of problems, fights,
questions over who shot first, etc. You’re going to help by
asking some of the patrons to leave. The cantina is a business,
so you’d like to ask as few as possible to leave. You need to
determine the size of the smallest set of characters
For example, in the first sample input below, Chewbacca and Grakchawwaa can converse, but nobody else understands Shyriiwook, so they can’t converse with others in the bar. If they leave, everyone else can converse. In the second sample input, Fran and Ian can converse, as can Polly and Spencer, but no other pairs of characters can converse, so either everyone but Polly and Spencer must leave or everyone but Fran and Ian.
Input
Input starts with a positive integer,
Output
Print a line of output giving the size of the smallest set
of characters
Sample Input 1 | Sample Output 1 |
---|---|
7 Jabba-the-Hutt Huttese Bib-Fortuna Huttese Basic Boba-Fett Basic Huttese Chewbacca Shyriiwook Basic Luke Basic Jawaese Binary Grakchawwaa Shyriiwook Basic Jawaese R2D2 Binary Basic |
2 |
Sample Input 2 | Sample Output 2 |
---|---|
6 Fran French Italian Enid English German George German Italian Ian Italian French Spanish Spencer Spanish Portugese Polly Portugese Spanish |
4 |