-
USER: tian tianbing [tbbd4261]
-
TASK: fenceLANG: C++ Compiling...Compile: OKExecuting...
-
Test 1: TEST OK [0.022 secs, 4016 KB]
-
Test 2: TEST OK [0.000 secs, 4016 KB]
-
Test 3: TEST OK [0.022 secs, 4016 KB]
-
Test 4: TEST OK [0.022 secs, 4016 KB]
-
Test 5: TEST OK [0.011 secs, 4016 KB]
-
Test 6: TEST OK [0.011 secs, 4016 KB]
-
Test 7: TEST OK [0.000 secs, 4016 KB]
-
Test 8: TEST OK [0.043 secs, 4016 KB]All tests OK.
-
Your program ('fence') produced all correct answers!
-
This is your submission #3 for this problem. Congratulations!
欧拉回路也可能是欧拉路径,用dfs,从小到大搜,要求是输出字典序小的.
刚开始是输出放在函数里面,这样后两组测试数据过不了,
/*
ID:tbbd4261
PROG:fence
LANG:C++
*/
#include<fstream>
using namespace std;
ifstream fin("fence.in");
ofstream fout("fence.out");
const int MAX=505;
int adj[MAX][MAX]={0},F,nmax=0;
int cnt[MAX]={0};
int print[1025*2+100]={0},len=0;
void dfs(int u)
{
//fout<<u<<endl;
for(int v=1; v<=nmax; v++)
if(adj[u][v])
{
adj[u][v]--;
adj[v][u]--;
dfs(v);
}
len++;
print[len]=u;
}
int main()
{
fin>>F;
int i,s,t;
for( i=1,s,t; i<=F; i++)
{
fin>>s>>t;
cnt[s]++;
cnt[t]++;
adj[s][t]++;
adj[t][s]++;
if(s>nmax)nmax=s;
if(t>nmax)nmax=t;
}
s=0;
for(i=1; i<=nmax; i++)
if(cnt[i]){
if(s==0)s=i;
if(cnt[i]%2==1){ s=i; break;}
}
dfs(s);
for(int j=len; j>=1; j--)
fout<<print[j]<<endl;
return 0;
}