DisjointStrings.hpp

struct DisjointStrings{
	DisjointStrings(QVector < QPair<QString, QString> > pairings = QVector < QPair<QString, QString> >()){
		if (pairings.empty()) return;

		QSet<QString> all_nodes;
		for (auto p : pairings) { all_nodes << p.first; all_nodes << p.second; }
		DisjointSet U(all_nodes.size());
		QMap < QString, int > node_idx;
		QMap < int, QString > idx_node;
		for (auto n : all_nodes) { node_idx[n] = node_idx.size(); idx_node[node_idx[n]] = n; }
		for (auto p : pairings) U.Union(node_idx[p.first], node_idx[p.second]);
		for (auto g : U.Groups()){
			QSet < QString > s;
			for (auto ni : g) s << idx_node[ni];
			groups << s;
		}
	}
	QVector < QSet<QString> > groups;
	QString representative(QString label){
		QString rep = "";
		for (auto g : groups){
			if (g.contains(label)){
				auto sorted = g.toList();
				qSort(sorted);
				rep = sorted.front(); // first element
				break;
			}
		}
		assert(rep.size());
		return rep;
	}
};