# ZOJ 3332 Strange Country II

Strange Country II

Time Limit: 1 Second      Memory Limit: 32768 KB      Special Judge

You want to visit a strange country. There are n cities in the country. Cities are numbered from 1 to n. The unique way to travel in the country is taking planes. Strangely, in this strange country, for every two cities A and B, there is a flight from A to B or from B to A, but not both. You can start at any city and you can finish your visit in any city you want. You want to visit each city exactly once. Is it possible?

Input

There are multiple test cases. The first line of input is an integer T (0 < T <= 100) indicating the number of test cases. Then T test cases follow. Each test case starts with a line containing an integer n (0 < n<= 100), which is the number of cities. Each of the next n * (n - 1) / 2 lines contains 2 numbers AB (0 < AB <= nA != B), meaning that there is a flight from city A to city B.

Output

For each test case:

• If you can visit each city exactly once, output the possible visiting order in a single line please. Separate the city numbers by spaces. If there are more than one orders, you can output any one.
• Otherwise, output "Impossible" (without quotes) in a single line.

Sample Input

```3
1
2
1 2
3
1 2
1 3
2 3```

Sample Output

```1
1 2
1 2 3
dfs#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>

using namespace std;
int a;
int ans;
int vis;
int n;
bool res;
void dfs(int x,int cnt)
{
if(cnt>n)
return;
if(res)
{
ans[cnt]=x;
return;
}
if(cnt==n)
{
res=true;
ans[cnt]=x;
return;

}
for(int i=1;i<=n;i++)
{
if(a[x][i]&&!vis[i])
{
vis[i]=1;
dfs(i,cnt+1);
vis[i]=0;
if(res)
{
ans[cnt]=x;
return;
}

}
}
}
int main()
{
int t;
int x,y;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
memset(a,0,sizeof(a));
for(int i=1;i<=n*(n-1)/2;i++)
{
scanf("%d%d",&x,&y);
a[x][y]=1;
}
memset(vis,0,sizeof(vis));
res=false;
for(int i=1;i<=n;i++)
{
vis[i]=1;
dfs(i,1);
vis[i]=0;
if(res)
break;
}
if(!res)
{
printf("Impossible\n");
continue;
}
for(int i=1;i<=n;i++)
{
if(i!=n)
printf("%d ",ans[i]);
else
printf("%d",ans[i]);
}
printf("\n");
}
return 0;
}```

0 条评论

## 相关文章

Median Weight Bead Time Limit: 1000MS Memory Limit: 30000K Total Submis...

35080

### hdu----149850 years, 50 colors(最小覆盖点)

50 years, 50 colors Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 3276...

29750

### hdu----（2586）How far away ？（DFS/LCA/RMQ）

How far away ？ Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/327...

29380

### POJ 3461 kmp

Oulipo Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 40168 ...

31460

### hdu----(3118)Arbiter(构造二分图)

Arbiter Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K ...

34550

### hdu---1506(Largest Rectangle in a Histogram/dp最大子矩阵)

Largest Rectangle in a Histogram Time Limit: 2000/1000 MS (Java/Others)    Memor...

29950

### SPOJ Number of Palindromes(回文树)

Number of Palindromes Time Limit: 100MS Memory Limit: 1572864KB 64bit I...

28760

### HDUOJ------2398Savings Account

Savings Account Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32...

32370

### HDUOJ------1058 Humble Numbers

Humble Numbers Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/327...

35980

### POJ 1651 Multiplication Puzzle(区间DP)

Multiplication Puzzle Time Limit: 1000MS Memory Limit: 65536K Total Sub...

33950 