欧拉回路问题,只要每次按编号从小到大找边,最后逆序输出欧拉路径即可。
#include <iostream>
#include <fstream>
#include <stack>
using namespace std;
ifstream fin("fence.in");
ofstream fout("fence.out");
#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif
int graph[501][501];
int degree[501];
int odd_degree_node[2];
int max_vertex = INT_MIN;
int min_vertex = INT_MAX;
int euler_path[1025];
int path_cnt;
void find_path(int vertex)
{
stack<int>s;
int t;
s.push(vertex);
while( !s.empty() ){
t = s.top();
if(degree[t]==0){
euler_path[path_cnt++] = t;
s.pop();
continue;
}
for(int i=min_vertex;i<=max_vertex;++i){
if( graph[t][i] ){
graph[t][i]--;
graph[i][t]--;
degree[t]--;
degree[i]--;
s.push(i);
break;
}
}
}
}
void solve()
{
int f;
in>>f;
int a,b;
while(f--){
in>>a>>b;
graph[a][b]++;
graph[b][a]++;
degree[a]++;
degree[b]++;
max_vertex = max(max_vertex,max(a,b));
min_vertex = min(min_vertex,min(a,b));
}
int odd_degree_cnt = 0;
for(int i=min_vertex;i<=max_vertex;++i){
if(degree[i]&1){
odd_degree_node[odd_degree_cnt++] = i;
}
}
int start = min_vertex;
if( odd_degree_cnt!=0){
start = odd_degree_node[0];
}
find_path(start);
for(int i=path_cnt-1;i>=0;--i)
out<<euler_path[i]<<endl;
}
int main(int argc,char *argv[])
{
solve();
return 0;
}