I'm writing a Settlers of Catan clone for a class. One of the extra credit features is automatically determining which player has the longest road. I've thought about it, and it seems like some slight variation on depth-first search could work, but I'm having trouble figuring out what to do with cycle detection, how to handle the joining of a player's two initial road networks, and a few other minutiae. How could I do this algorithmically?

For those unfamiliar with the game, I'll try to describe the problem concisely and abstractly: I need to find the longest possible path in an undirected cyclic graph.