/************************* TWICEAROUNDMST.H ***********************************
* TSP Algorithms : TwiceAroundMST                                  21.11.2008 *
*                                                                             *
* - Find a minimum-weight spanning tree T of G;                               *
* - Conduct a DFS of T: associate a DFS index L(v) with each vertex;          *
* - Output the following cycle:                                               *
*   C = vi1,vi2,…,vin,vi1 where L(vij) = j                                    *
*                                                             Beycan Kahraman *
******************************************************************************/

#pragma once
#include "AlgorithmTSP.h"
#include <algorithm>
#include <vector>
#include <cstdio>

class TwiceAroundMST :
	public AlgorithmTSP
{
private:
	int mst_cost;
	int count;
	void KruskalLikeMST();
	void RecursiveDeepFirstSearch();
	void DeepFirstSearch();
public:
	TwiceAroundMST(short dist[][SZ], int n);
	virtual void Run();
	~TwiceAroundMST(void);
};
