USACO OPEN11 Problem 'oddd' Analysis

by Neal Wu

Suppose we have chosen a subset of the paths that satisfies the constraint that all towns have odd degree. Since the sum of the degree of each town must be even (as we are counting each chosen path twice), we can immediately see that if N is odd there does not exist a solution, as the sum of an odd number of odd degrees must be odd.

Furthermore, we can see that if we decompose the graph into its connected components, since we must solve each component independently, there cannot exist a solution if any component has an odd number of towns. (Indeed this makes sense, as an odd-sized graph cannot be broken down into only even-sized subgraphs.) We now claim that if every connected component of the graph has an even number of towns, then a solution exists. We provide a construction as follows:

For a connected component of size n (n even), find any spanning tree of the graph and root it at an arbitrary node R. We assign edges of the tree to be either on or off as follows:

• For each vertex v from the bottom leaves up to (but not including) R, we assign the edge from v to its parent to be either on or off so that v has an odd number of on edges adjacent to it.
• Since the other n - 1 vertices of the tree have odd degree and n is even, by parity R must have an odd number of adjacent on edges as well, so we are done.

To implement the above algorithm we can simply perform a depth-first search on each component. Sample code (from Travis Hance) follows:

#include <cstdio>
#include <vector>
using namespace std;

#define nmax 50005

vector<int> edges[nmax];
vector<int> edgesi[nmax];
bool visited[nmax];
vector<int> answer;

bool dfs(int a, int pa, int edgei) {
	if(visited[a]) {
		return false;
	}
	visited[a] = true;

	int count = 0;
	for(int i = 0; i < edges[a].size(); i++) {
		if(edges[a][i] != pa) {
			if(dfs(edges[a][i], a, edgesi[a][i]))
				count++;
		}
	}

	if(count % 2 == 0) {
		answer.push_back(edgei);
		return true;
	}
	return false;
}

int main() {
	freopen("oddd.in","r",stdin);
	freopen("oddd.out","w",stdout);

	int n, m;
	scanf("%d", &n);
	scanf("%d", &m);
	for(int i = 0; i < n; i++)
		visited[i] = false;
	for(int i = 0; i < m; i++) {
		int a, b;
		scanf("%d", &a);
		scanf("%d", &b);
		a--;
		b--;
		edges[a].push_back(b);
		edges[b].push_back(a);
		edgesi[a].push_back(i);
		edgesi[b].push_back(i);
	}

	for(int i = 0; i < n; i++) {
		if(!visited[i]) {
			if(dfs(i, -1, -1)) {
				printf("-1\n");
				return 0;
			}
		}
	}

	printf("%d\n", answer.size());
	for(int i = 0; i < answer.size(); i++)
		printf("%d\n", answer[i] + 1);
}