UVa302 - John's trip(并查集、欧拉回路、DFS)

#include <cstdio>#include <vector>#include <utility>#include <cstring>#include <climits>#include <algorithm>usingnamespacestd;
constintN=2000;
intdeg[N];
vector<pair<int, int>>adjList[N];
boolvis[N];
intans[N];
inttop;
intstart;
boolinput();
voidadd(intx, inty, intz);
voidsolve();
voiddfs(intu);
intmain()
{
#ifndef ONLINE_JUDGEfreopen("d:\\OJ\\uva_in.txt", "r", stdin);
#endifwhile (input()) {
solve();
    }
return0;
}
boolinput()
{
intx, y, z;
scanf("%d%d", &x, &y);
if (x==0&&y==0) returnfalse;
start=min(x, y);
for (inti=0; i<N; i++) adjList[i].clear();
memset(deg, 0x00, sizeof(deg));
while (1) {
scanf("%d", &z);
add(x, y, z);
deg[x]++;
deg[y]++;
scanf("%d%d", &x, &y);
if (x==0&&y==0) break;
   }
returntrue;
}
voidadd(intx, inty, intz)
{
adjList[x].push_back(make_pair(z, y));;
adjList[y].push_back(make_pair(z, x));;
}
voidsolve()
{
boolok=true;
for (inti=0; i<N; i++) {
if (!adjList[i].empty()) {
if (deg[i] &1) {
ok=false;
break;
            }
sort(adjList[i].begin(), adjList[i].end());
        }
    }
if (!ok) {
printf("Round trip does not exist.\n\n");
return;
    }
top=0;
memset(vis, false, sizeof(vis));
dfs(start);
for (inti=top-1; i>=0; i--) {
printf("%d%s", ans[i], i?" ":"\n\n");
    }
}
voiddfs(intu)
{
for (size_ti=0; i<adjList[u].size(); i++) {
if (!vis[adjList[u][i].first]) {
vis[adjList[u][i].first] =true;
dfs(adjList[u][i].second);
ans[top++] =adjList[u][i].first;
        }
    }
}