How exactly does recursion work with iterators?

[wolle]

I've come up with a solution now according to the strategy in my post #4.

I've cleaned up my solution in #10. It turns out that the second part of the solution strategy isn't necessary. Once it's known how many astronauts there are in an urn it's possible to calculate how much they contribute to the total pairs of astronauts from different countries. The contribution from astronauts that aren't in any urn can be calculated once the total number of astronauts that are in urns is known. This observation greatly simplifies the code.

#include <iostream>
#include <vector>
#include <utility>
#include <unordered_set>
#include <functional>
#include <algorithm>
#include <stack>

namespace tomoon {

	using Astro = int;
	using Pair = std::pair<Astro,Astro>;
	using PairList = std::vector<Pair>;

	class PairBase { // pair storage
	public:

		PairBase(const PairList& pairs) {
			for (Pair p : pairs) {
				storage.emplace(p); // store all pairs
				storage.emplace(reverse_pair(p)); // and reversed pairs
			}
		}

		void remove_pair(Pair p) { // remove pair 
			const auto rem = [&] (const Pair p) {
				const auto range = storage.equal_range(p); // here equal is on first of pair (as defined for Pairs in the storage hashtable)
				const auto iterator = std::find(range.first, range.second, p); // here equal is on both first and second (standard for an std::pair)
				if (iterator != range.second) storage.erase(iterator);
			};
			rem(p);
			rem(reverse_pair(p));
		};

		Pair any_pair() const { // pick any pair (for example the first)
			return *storage.begin();
		};

		bool no_pairs() const { // no more pairs ?
			return storage.empty();
		};

		PairList linked_pairs(Pair p) const { 	// identify all pairs that are linked (share an astronout) with this pair
			PairList pairList;
			const auto add = [&] (const Pair p) {
				const auto range = storage.equal_range(p);
				pairList.insert(pairList.end(), range.first, range.second);
			};
			add(p);
			add(reverse_pair(p));
			return pairList;
		}

	private:
		struct Hash {
			std::size_t operator() (Pair p) const { return std::hash<Astro>{}(p.first); }
		};
		struct Equal {
			bool operator() (Pair l,Pair r) const { return l.first == r.first; };
		};
		     // hash table for pairs, equal relation and hashing is on first astronaut of a pair 
		std::unordered_multiset<Pair,Hash,Equal> storage; // pair storage

		Pair reverse_pair(Pair p) const { // switch first with second in pair
			return Pair(p.second,p.first);
		};
	}; // PairBase


	inline int journey(const int astros,const PairList& pairs) {
		PairBase pairBase(pairs); // pair storage

		int comb_sum = 0; // total sum of astronaut not from same country combinations
		int urn_sum = 0; // sum of austronauts in urns

		while (!pairBase.no_pairs()) { // as long as there are pairs
			std::stack<Pair> stack; // stack of pairs
			std::unordered_set<Astro> urn; // urn of austronauts

			stack.push(pairBase.any_pair()); // push any pair
			while (!stack.empty()) { // when empty all astronouts from a common country have been identified
				const Pair p = stack.top(); // pop a pair
				stack.pop();
				pairBase.remove_pair(p); // remove pair 
				urn.insert({p.first,p.second}); // store both astronauts of pair
				for(const Pair q : pairBase.linked_pairs(p)) stack.push(q); // push all linked pairs on stack
			}

			const int n = int(urn.size()); // number of astros in this urn
			urn_sum += n; // add to total urn sum
			comb_sum += n * (astros - n); // multiply astros inside this urn with all other astros and add up total sum
		}
		comb_sum += (astros - urn_sum) * (astros - 1); // consider astros outside any urn
		comb_sum /= 2; // all combinations have been counted twice

		return comb_sum; //comb_sum;
	}

} // tomoon

void test() {

	// sample 0 from problem description
	tomoon::PairList pairs_sample_0 ={
		//		{5, 3}, // not a pair, 5 astronauts
				{0,1},
				{2,3},
				{0,4}
	};
	int result_0 = tomoon::journey(5,pairs_sample_0);
	std::cout << "Result 0 = " << result_0 << std::endl; // 6 as it should
	std::cout << "----------" << std::endl; // 5 as it should

											// sample 1 from problem description
	tomoon::PairList pairs_sample_1 ={
		//		{4, 1}, // not a pair, 4 astronauts
				{0,2}
	};
	int result_1 = tomoon::journey(4,pairs_sample_1);
	std::cout << "Result 1 = " << result_1 << std::endl; // 5 as it should
	std::cout << "----------" << std::endl; // 5 as it should

	tomoon::PairList pairs_sample_2 ={
		//		{100, 70},
				{0,11},
				{2,4},
				{2,95},
				{3,48},
				{4,85},
				{4,95},
				{5,67},
				{5,83},
				{5,42},
				{6,76},
				{9,31},
				{9,22},
				{9,55},
				{10,61},
				{10,38},
				{11,96},
				{11,41},
				{12,60},
				{12,69},
				{14,80},
				{14,99},
				{14,46},
				{15,42},
				{15,75},
				{16,87},
				{16,71},
				{18,99},
				{18,44},
				{19,26},
				{19,59},
				{19,60},
				{20,89},
				{21,69},
				{22,96},
				{22,60},
				{23,88},
				{24,73},
				{27,29},
				{30,32},
				{31,62},
				{32,71},
				{33,43},
				{33,47},
				{35,51},
				{35,75},
				{37,89},
				{37,95},
				{38,83},
				{39,53},
				{41,84},
				{42,76},
				{44,85},
				{45,47},
				{46,65},
				{47,49},
				{47,94},
				{50,55},
				{51,99},
				{53,99},
				{56,78},
				{66,99},
				{71,78},
				{73,98},
				{76,88},
				{78,97},
				{80,90},
				{83,95},
				{85,92},
				{88,99},
				{88,94}
	};
	int result_2 = tomoon::journey(100,pairs_sample_2);
	std::cout << "Result 2 = " << result_2 << std::endl;
	std::cout << "----------" << std::endl;

	tomoon::PairList pairs_sample_3 ={
		//{10, 7},
		{0,2},
		{1,8},
		{1,4},
		{2,8},
		{2,6},
		{3,5},
		{6,9}
	};
	int result_3 = tomoon::journey(10,pairs_sample_3);
	std::cout << "Result 3 = " << result_3 << std::endl;
	std::cout << "----------" << std::endl;


	tomoon::PairList pairs_sample_4 ={
		//		{10, 20},
		{0,1},
		{0,3},
		{0,4},
		{1,2},
		{1,3},
		{1,5},
		{1,7},
		{1,8},
		{1,9},
		{2,8},
		{2,7},
		{3,5},
		{3,8},
		{3,7},
		{4,9},
		{4,5},
		{4,6},
		{4,7},
		{6,8},
		{6,7}
	};
	int result_4 = tomoon::journey(10,pairs_sample_4);
	std::cout << "Result 4 = " << result_4 << std::endl;
	std::cout << "----------" << std::endl;

	tomoon::PairList pairs_sample_5 ={
		//		{10000, 2},
		{1,2},
		{3,4}
	};
	int result_5 = tomoon::journey(10000,pairs_sample_5);
	std::cout << "Result 5 = " << result_5 << std::endl;
	std::cout << "----------" << std::endl;
}