Miscellany

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <stdio.h>
using namespace std;
struct Res;

struct Node {
	
	char id;
	vector<Res*> conn;
};

struct Res {
	Res() : valeur(1.0) { }
	double valeur;
	
	Node *a, *b;
	
	bool operator==(const Res& other) {
		return a->id == other.a->id && b->id == other.b->id;
	}
	
/*	bool operator<(const Res& other) {
		return a->id < other.a->id;
	}*/
};

bool composition(Res* a, Res* b) {
	if(a->a->id == b->a->id)
		return a->b->id < b->b->id;
	else
		return a->a->id < b->a->id;
}

bool removeDeadEnds(map<char, Node*>& nodes, multiset<Res*,bool (*)(Res*, Res*)>& resistances)
{	
	// Identify dead ends
	vector<char> deadEnds;
	for (map<char, Node*>::iterator it = nodes.begin(); it != nodes.end(); it++)
	{
		if ((it->second)->id == 'a' || (it->second)->id == 'z')
		{
			continue;
		}

		if ((it->second)->conn.size() < 2)
		{
			deadEnds.push_back(it->first);
		}
	}

	for (int i = 0; i < deadEnds.size(); i++)
	{
		Node* thisNode = nodes[deadEnds[i]];
		Res* res = thisNode->conn[0];
		Node* otherNode = (res->a == thisNode) ? res->b : res->a;

		otherNode->conn.erase(
			remove(otherNode->conn.begin(), otherNode->conn.end(), res),
			otherNode->conn.end());
		
		resistances.erase(res);

		nodes.erase(deadEnds[i]);

		delete res;
		delete thisNode;
	}

	return deadEnds.size() != 0;
}

void reduceRes(multiset<Res*,bool (*)(Res*, Res*)>& res, vector<Res*>& resToReduce)
{
	Node* newA = resToReduce[0]->a;
	Node* newB = resToReduce[0]->b;

	printf("Parallele: Merging between %c and %c\n", newA->id, newB->id);

	

	double resValue = 0;
	for (unsigned int i = 0; i < resToReduce.size(); i++)
	{
		// Do some clean up
		res.erase(resToReduce[i]);
	
		// Accumulate the res values
		resValue += 1 / resToReduce[i]->valeur; 

		newA->conn.erase(
			remove(newA->conn.begin(), newA->conn.end(), resToReduce[i]),
			newA->conn.end());
		newB->conn.erase(
			remove(newB->conn.begin(), newB->conn.end(), resToReduce[i]),
			newB->conn.end());

		delete resToReduce[i];
	}

	resValue = 1 / resValue;
	

	Res* newRes = new Res();
	newRes->a = newA;
	newRes->b = newB;
	newRes->valeur = resValue;

	res.insert(newRes);

	newA->conn.push_back(newRes);
	newB->conn.push_back(newRes);
}
 
bool reduce_parallel (multiset<Res*,bool (*)(Res*, Res*)>& res)
{
	multiset<Res*,bool (*)(Res*, Res*)>::iterator it = res.begin();
	vector<Res*> resToReduce;

	resToReduce.push_back(*it);

	it++;

	while(it != res.end())
	{
		// If it's the same, add it to the res to reduce
		if (*(*it) == *(resToReduce[0]))
		{
			resToReduce.push_back(*it);
		}
		else if (resToReduce.size() == 1) // If not, but there is only one res in the stack
		{ // change it for the current one
			resToReduce[0] = *it;
		}
		else // If it's different and we have multiple element in the stack, reduce them and return
		{
			reduceRes(res, resToReduce);
			return true;
		}
		
		it++;
	}

	// If we finish and the stack has some element, reduce them
	if (resToReduce.size() > 1)
	{
		reduceRes(res, resToReduce);
		return true;
	}

	return false;
}

bool reduce_serie(map<char, Node*>& nodes, multiset<Res*,bool (*)(Res*, Res*)>& res) {
	for (map<char, Node*>::iterator it = nodes.begin(); it != nodes.end(); it++) {
		Node* node = it->second;
		if (node->id == 'a' || node->id == 'z') {
			continue;
		}
		
		if (node->conn.size() == 2) {
			//printf("Au debut  de --, res.size = %d\n", res.size());
			Res* r0 = node->conn[0];
			Res* r1 = node->conn[1];
			if (r0->a->id > r1->a->id) {
				r0 = node->conn[1];
				r1 = node->conn[0];
			}
			
			// Aller chercher les references vers les deux noeuds voisins
			Node *n0 = r0->a;
			Node *n1 = r1->b;
			
			printf("Serial: Merging %c-%c with %c-%c\n", n0->id, node->id, node->id, n1->id);
			
			// Creer notre nouvelle resistance
			Res* r_new = new Res();
			r_new->valeur = r0->valeur + r1->valeur;
			
			// Enlever les anciennes resistances
			
			
			n0->conn.erase(remove(n0->conn.begin(), n0->conn.end(),r0), n0->conn.end());
			n1->conn.erase(remove(n1->conn.begin(), n1->conn.end(),r1), n1->conn.end());
			
			//printf("1Au debut  de --, res.size = %d\n", res.size());
			res.erase(r0);
			//printf("2Au debut  de --, res.size = %d\n", res.size());
			res.erase(r1);
			//printf("3Au debut  de --, res.size = %d\n", res.size());
			delete r0;
			delete r1;
			
			if (n0->id > n1->id) {
				r_new->a = n1;
				r_new->b = n0;
			} else {
				r_new->a = n0;
				r_new->b = n1;
			}
			res.insert(r_new);
			
			
			
			
			// Ajouter la nouvelle resistance
			n0->conn.push_back(r_new);
			n1->conn.push_back(r_new);
			
			// Enlever le noeud
			nodes.erase(it);
			delete node;
			
			//printf("A la fin de --, res.size = %d\n", res.size());
			
			return true;
		}
	}
	
	return false;
}

bool cochon = false;

void solve_one() {
	map<char, Node*> nodes;
	bool (*fn_pt)(Res*, Res*) = composition;
	multiset<Res*,bool (*)(Res*, Res*)> res(fn_pt);
	
	string line;
	
	getline(cin, line);
	const char *str = line.c_str();
	//printf("Teh string: '%s'\n", str);
	
	
	const char *c = str;
	
	for (;;) {
		char n0_id = *c;
		c++;
		char n1_id = *c;
		c++;
		
		Node *n0, *n1;
		
		if (nodes.find(n0_id) != nodes.end()) {
			n0 = nodes[n0_id];
		} else {
			n0 = new Node();
			n0->id = n0_id;
			nodes.insert(make_pair(n0_id, n0));
		}
		
		if (nodes.find(n1_id) != nodes.end()) {
			n1 = nodes[n1_id];
		} else {
			n1 = new Node();
			n1->id = n1_id;
			nodes.insert(make_pair(n1_id, n1));
		}
		
		Res *new_res = new Res();
		if (n0->id > n1->id) {
			new_res->a = n1;
			new_res->b = n0;
		} else {
			new_res->a = n0;
			new_res->b = n1;
		}
		
	//	printf("Creating res %c %c\n", n0->id, n1->id);
		
		res.insert(new_res);
		n0->conn.push_back(new_res);
		n1->conn.push_back(new_res);
		
		
		if (*c == '\0') {
			break;
		}
		c++;
	}

	while (res.size() > 1) {
	//printf("Res size = %d\n", res.size());
		//printf("Let's try //\n");
		while (reduce_parallel(res)) { /*printf("Let's try //\n");*/ }
		//printf("Let's try --\n");
		while (reduce_serie(nodes, res)) { /*printf("Let's try --\n"); */}
		while (removeDeadEnds(nodes, res));
	}
	//printf("Res size = %d\n", res.size());
	if (!cochon)
	printf("%.4f\n", (*(res.begin()))->valeur);
	else 
	printf("%.4f", (*(res.begin()))->valeur);
}

int main() {
	
	
	int N;
	
	cin >> N;
	cin.ignore(1);
	for (int i = 0; i < N; i++) {
		//printf("Problem %d\n", i);
		if (i + 1 == N)
			cochon = !cochon;
		solve_one();

	}
	
}