Category Archives: Euler

USACO 3.3.1 – Riding the fences


#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

int start=-1,ct=0,cr[10024]={0},g[501][501]={{0}},deg[501]={0};

void loop(int n) {
	for (int j = 1; j < 501; j++)
		if (g[n][j])
			g[n][j]--, g[j][n]--, loop(j);
	cr[ct++] = n;
}
int main() {
	freopen("fence.in", "r", stdin), freopen("fence.out", "w", stdout);
	int F, a, b, start = 0, mod = 0;
	cin >> F;
	while (F-- && cin >> a >> b)
		g[a][b]++, g[b][a]++, deg[a]++, deg[b]++;
	for (int i = 500; i >= 0; i--)
		mod = deg[i] % 2 ? i : mod, start = deg[i] ? i : start;
	loop(mod ? mod : start);
	for (int c = ct - 1; c >= 0; c--)
		cout << cr[c] << endl;
	return 0;
}
Advertisements