#OJ2288. 旅行计划
旅行计划
旅行计划
Time Limit: 5 Sec Memory Limit: 128 MB
Description
sgxz学长要去n个城市旅行,其中每个城市都有若干直达其他城市的车票。sgxz学长想设计一个路线,能够从第一个城市出发,经过且只经过其他每个城市各一次,最后回到第一个城市。求出所有可行的旅行路线。
Input
第一行为一个正整数T,代表样例组数。 每组样例的第一行为一个正整数n(2<=n<=12),代表城市数量。 接下来有n行,每行第一个数为一个正整数m(1<=m<=n-1),代表每个城市(从1到n)能够直达的其他城市(不包含i本身)的数量,接下来有m个正整数,代表第i个城市能够直达的其他城市。 除Sample外,所有测试数据均为随机生成。
Output
对于每组样例,第一行输出Case #x:,x为样例序号。 接下来按字典序从小到大输出所有从第一个城市出发,经过所有城市各一次再回到第一个城市的路线。若没有可行路线,则不输出。
Sample Input
3
2
1 2
1 1
3
2 2 3
2 1 3
2 1 2
3
1 2
1 3
1 1
Sample Output
Case #1:
1 2 1
Case #2:
1 2 3 1
1 3 2 1
Case #3:
1 2 3 1
HINT
由于要求按字典序输出,可以考虑用vector数组存储相邻结点并排序。也可以尝试使用map。