2014
03-23

Tour Route

The city is so crowded that the mayor can’t bear any longer. He issued an order to change all the roads into one-way street. The news is terrible for Jack, who is the director of a tourism company, because he has to change the travel route. All tourists want to set out from one scenic spot, then go to every scenic spots once and only once and finally return to the starting spot. They don’t care about which spot to start from, but they won’t go back to the starting spot before they have visited all other spots. Fortunately, the roads in the city have been perfectly built and any two scenic spots have been connected by ONE road directly. Jack gives the map of the city to you, and your task is to arrange a new travel route around the city which can satisfy the tourists.

Input consists of multiple test cases and ends with a line of “0”.
For each test case:
The first line contains a single integer n (0<n<=1000), representing the number of city scenic spots. Scenic spots are numbered form 1 to n.
Then n lines follows, and each line consists of n integers. These n lines make a matrix. If the element in the ith row and the jth column is 1(i≠j), it means that the direction of the road between spot i and spot j is from spot i to spot j. If that element is 0, it means that the road’s direction is from spot j to spot i. The numbers in the main diagonal of the matrix are all 0. (i and j start from 1)

Input consists of multiple test cases and ends with a line of “0”.
For each test case:
The first line contains a single integer n (0<n<=1000), representing the number of city scenic spots. Scenic spots are numbered form 1 to n.
Then n lines follows, and each line consists of n integers. These n lines make a matrix. If the element in the ith row and the jth column is 1(i≠j), it means that the direction of the road between spot i and spot j is from spot i to spot j. If that element is 0, it means that the road’s direction is from spot j to spot i. The numbers in the main diagonal of the matrix are all 0. (i and j start from 1)

5
0 0 1 1 1
1 0 1 1 0
0 0 0 1 0
0 0 0 0 1
0 1 1 0 0
2
0 1
0 0
0

1 3 4 5 2
-1

Tour Route
Time Limit:
20000/10000 MS
(Java/Others)    Memory
Limit: 32768/32768 K (Java/Others)
Total Submission(s):
466    Accepted
Submission(s): 80
Special Judge
Problem Description
The city is so crowded that the mayor can’t bear any longer.
He issued an order to change all the roads into one-way street. The
news is terrible for Jack, who is the director of a tourism
company, because he has to change the travel route. All tourists
want to set out from one scenic spot, then go to every scenic spots
once and only once and finally return to the starting spot. They
don’t care about which spot to start from, but they won’t go back
to the starting spot before they have visited all other spots.
Fortunately, the roads in the city have been perfectly built and
any two scenic spots have been connected by ONE road directly. Jack
gives the map of the city to you, and your task is to arrange a new
travel route around the city which can satisfy the tourists.
Input
Input consists of multiple test cases and ends with a line of
“0”.
For each test case:
The first line contains a single integer n (0
Then n lines follows, and each line consists of n integers. These n
lines make a matrix. If the element in the ith row and the jth
column is 1(i≠j), it means that the direction of the road between
spot i and spot j is from spot i to spot j. If that element is 0,
it means that the road’s direction is from spot j to spot i. The
numbers in the main diagonal of the matrix are all 0. (i and j
start from 1)
Output
For each test case, print all the spots No. according to the
traveling order of the route in one line. If multiple routes exist,
just print one of them. If no such route exists, print a “-1”
instead. Because the starting spot is the same as the ending spot,
so you don’t need to print the ending spot.
This problem needs special judge.
Sample Input
5
0 0 1 1
1
1 0 1 1
0
0 0 0 1
0
0 0 0 0
1
0 1 1 0
0
2
0 1
0 0
0
Sample Output
1 3 4 5
2
-1
======================================================================================

Tarjan是线性效率所以我并不担心。

======================================================================================
#include<cstdio>
const int N = 1000;
bool g[N][N];
int n , next[N];
bool expand( int s )
{
for( int i = 0 ; i
< n ; next[i++] = -1 );
int front = s , back =
front;
for( int i = 0 ; i
< n ; i++ )
{
if( i == s )
continue;
if( g[i][front] )   next[i] =
front , front = i;
else
{
int a =
front , b = next[front];
while( b
!= -1 && g[b][i] )
a = b , b = next[b];
next[a] =
i;
next[i] =
b;
if( b ==
-1 )   back = i;
}
}
if( g[back][front]
)
{
next[back] = front;
return true;
}
return false;
}
bool solve()
{
for( int i = 0 ; i
< n ; i++ )
if( expand(i) )  return
true;
return false;
}
int main()
{
while(
scanf(“%d”,&n) , n )
{
for( int i = 0 ; i < n ; i++
)
for( int j
= 0 ; j < n ; j++ )
scanf(“%d”,&g[i][j]);
if( n == 1 )   puts(“1″);
else if( n == 2 || !solve() )
puts(“-1″);
else
for( int i
= 0 , j = 0 ; i < n ; i++ , j = next[j] )
printf(“%d%c”,j+1,i==n-1?’\n’:’ ‘);
}
return 0;
}

1. 思路二可以用一个长度为k的队列来实现，入队后判断下队尾元素的next指针是否为空，若为空，则出队指针即为所求。