UVA10054 The Necklace

    • 64通过
    • 251提交
  • 题目来源 UVA 10054
  • 评测方式 RemoteJudge
  • 标签 并查集
  • 难度 提高+/省选-
  • 时空限制 3000ms / 0MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    题目大意:有一种由彩色珠子连接而成的项链。每个珠子的两半由不同颜色组成。如图所示,相邻两个珠子在接触的地方颜色相同。现在有一些零碎的珠子,需要确认它们是否可以复原成完整的项链。

    输入格式:输入第一行为测试数据组数 T 。每组数据的第一行是一个整数N (5 ≤ N ≤ 1000 ),表示珠子的个数。接下来的N 行每行包含两个整数,即珠子两半的颜色。颜色用1~50的整数来表示。

    输出格式:对于每组数据,输出测试数据编号和方案。如果无解,输出“some beads may be lost”。方案的格式和输入相同,也是一共N 行,每行用两个整数描述一个珠子(从左到右的顺序),其中第一个整数表示左半的颜色,第二个整数表示右半的颜色。根据题目规定,对于1≤i≤N-1,第i行的第二个数必须等于第i+1行上的第一个数,且第_N_行的第二个数必须等于第一行的第一个数(因为项链是环形的)。如果有多解,输出任意一组即可。在相邻两组输出之间应有一个空行。

    感谢@ty_rj 提供的翻译

    题目描述

    PDF

    输入输出格式

    输入格式:

    输出格式:

    输入输出样例

    输入样例#1: 复制
    2
    5
    1 2
    2 3
    3 4
    4 5
    5 6
    5
    2 1
    2 2
    3 4
    3 1
    2 4
    输出样例#1: 复制
    Case #1
    some beads may be lost
    Case #2
    2 1
    1 3
    3 4
    4 2
    2 2
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。