Playing With Domino
Time limit1sMemory limit128 MB
Given up to 1000 dominoes with faces numbered 0 to 6, find the largest number of tiles that can be linked in a single chain where touching squares match.
- Level
Medium6 of 10
- Topics
- Graph, DFS, Brute force, Implementation
- Solved
- No attempts yet
Problem
A domino is a 2x1 rectangular tile whose face is split into two squares, each showing from 0 to 6 dots. Many games arrange dominoes into a single chain in which every two neighbouring dominoes touch on squares that show the same number of dots.
A full domino set has 28 distinct faces: 0-0, 0-1, 0-2, 0-3, 0-4, 0-5, 0-6, 1-1, 1-2, 1-3, 1-4, 1-5, 1-6, 2-2, 2-3, 2-4, 2-5, 2-6, 3-3, 3-4, 3-5, 3-6, 4-4, 4-5, 4-6, 5-5, 5-6, 6-6. A domino may be laid in either orientation, so a 1-6 tile can be used as 1/6 or 6/1.
Given a collection of dominoes (the same face may appear more than once), find the greatest number of dominoes that can be arranged into one such chain.
Input
The input contains several test cases and continues until end of file.
Each test case begins with an integer N (1 <= N <= 1000), the number of available dominoes. Each of the next N lines contains two integers between 0 and 6 describing one domino; the first integer is never greater than the second.
Output
For each test case, print on its own line the number of dominoes in the longest chain that can be formed.