The main issue is that C version is hardly functional programming: stuff like array<int,3> for forest and then counting instead of massive branching like java's isStable();
Reserving the entire next_forests like that:
next_forests.reserve(forests.size() * possible_meals.size());
helps quite a lot compared to the small header-full instances Java features.