← 返回 apple 的题目列表Merge Synonym Groups
类型：online_judge
Given a list of string pairs pairs, where pairs[i] = [word1, word2] means that word1 and word2 are synonyms (aliases).
The synonym relation is:
Bidirectional: if a is a synonym of b, then b is a synonym of a.
Transitive: if a is a synonym of b and b is a synonym of c, then a, b, and c belong to the same synonym group.
Merge all words that are directly or indirectly related. Return a mapping where:
The key is the lexicographically smallest word in a synonym group.
The value is the list of all words in that group, sorted in lexicographical order.
Input Format
First line: an integer n, the number of word pairs.
Next n lines: two non-empty space-separated strings, word1 word2.
Output Format
Print one group per line in ascending lexicographical order of its key:
key: word1 word2 ...
Words within each group must also be in ascending lexicographical order.
Example 1
Input:
3
a b
b c
d e
Output:
a: a b c
d: d e
Example 2
Input:
4
fast quick
quick rapid
slow sluggish
rapid speedy
Output:
fast: fast quick rapid speedy
slow: slow sluggish
Constraints
1 <= n <= 100000
Each word contains comparable non-whitespace characters.
The total number of distinct words is at most 200000.
Example
Input
3
a b
b c
d e
Output
a: a b c
d: d e