Solução: Problema do grafo conexo (Thiago Freire)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
 
public class Graph {
 
	private HashMap<Integer, ArrayList<Integer>> adj = new HashMap<Integer, ArrayList<Integer>>();
 
	private void addVertex(int v) {
		adj.put(new Integer(v), new ArrayList<Integer>());
	}
 
	private void removeVertex(int v) {
		adj.remove(v);
	}
 
	private Integer getFirstVertex() {
		return adj.keySet().iterator().next();
	}
 
	private void addEdge(int u, int v) {
		if (!adj.containsKey(u)) 
			addVertex(u);
		if (!adj.containsKey(v)) 
			addVertex(v);
		adj.get(u).add(v);
		adj.get(v).add(u);
	}
 
	private boolean hasNeighbors(int v) {
		return !adj.get(v).isEmpty();
	}
 
	private int getFirstNeighbor(int v) {
		return adj.get(v).get(0);
	}
 
	private void removeFirstNeighbor(int v) {
		adj.get(v).remove(0);
	}
 
	private int isConnected() {
		HashSet<Integer> possibleKeys = new HashSet<Integer>();
		HashSet<Integer> keys = new HashSet<Integer>();
		int v;
 
		possibleKeys.add(getFirstVertex());
		while (!possibleKeys.isEmpty()) {
			v = possibleKeys.iterator().next();
			keys.add(v);
			while (hasNeighbors(v)) {
				if (!keys.contains(getFirstNeighbor(v)))
					possibleKeys.add(getFirstNeighbor(v));
				removeFirstNeighbor(v);
			}
			removeVertex(v);
			possibleKeys.remove(v);
		}
 
		return adj.isEmpty() ? 1 : 0;
	}
 
	public static void main(String[] args) throws IOException {
		Graph g = new Graph();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] vertices;
 
		int n = Integer.parseInt(br.readLine());
		for (int i = 0; i < n; i++) {
			vertices = br.readLine().split(" ");
			g.addEdge(Integer.parseInt(vertices[0]), Integer.parseInt(vertices[1]));
		}
		System.out.println(g.isConnected());
	}
}