#include <iostream>
#include <vector>
#include <deque>
#include <cmath>
#include <cstdlib>
#include <map>
#include <list>

using namespace std;

class vertex {
public:
  vertex(int index) : index(index), rank(0) {parent = this;}

  int index;
  vertex* parent;
  int rank;

  vertex* findNaive() {
    vertex* v = this;
    while (v->parent != v)
      v = v->parent;
    return v;
  }

  vertex* findPathCompression() {
    vertex* v = this;
    while (v->parent != v)
      v = v->parent;
    vertex* root = v;
    v = this;
    vertex* nextV;
    while (v->parent != v) {
      nextV = v->parent;
      v->parent = root;
      v = nextV;
    }
    return v;
  }

  void unionNaive(vertex* other) {
    this->parent = other;
  }

  void unionLinkByRank(vertex* other) {
    this->parent = other;
    if (rank == other->rank)
      other->rank++;
  }

  bool rem(vertex* other) { // returns true, if both in different sets
    if (index < other->index) {
      if (this == parent) {
	parent = other->parent;
	return true;
      }
      return parent->rem(other);
    } else if (index > other->index) {
      if (other == other->parent) {
	other->parent = parent;
	return true;
      }
      return rem(other->parent);
    } // else index == other->index
    return false;
  }

  bool sp_rem(vertex* other) { //returns true, if both in different sets
    vertex* nextV;
    if (index < other->index) {
      if (this == parent) {
	parent = other->parent;
	return true;
      }
      nextV = parent;
      if (parent->index < other->parent->index) {
	parent = other->parent;
      }
      return nextV->rem(other);
    } else if (index > other->index) {
      if (other == other->parent) {
	other->parent = parent;
	return true;
      }
      nextV = other->parent;
      if (other->parent->index < parent->index) {
	other->parent = parent;
      }
      return rem(nextV);
    } // else index == other->index
    return false;
  }
};

map<short, vector<pair<int, int> > > edgeWeights;
deque<vertex*> sets;
list<pair<int, int> > spanningTree;
int totalCost = 0;

void createEdges(int numberOfVertices);
void makeSet(int index);
bool performNaiveUnionFind(int numberOfVertices);
bool performLRPC(int numberOfVertices);
bool performREM(int numberOfVertices);
bool performSP_REM(int numberOfVertices);
void cleanup();

int main(int argc, char** argv) {
  if (argc != 2) {
    cerr << "call: A4_3 <index>" << endl;
    cerr << "   with index being:" << endl;
    cerr << "      1: naive find and naive union" << endl;
    cerr << "      2: LRPC" << endl;
    cerr << "      3: REM" << endl;
    cerr << "      4: SP-REM" << endl;
    exit(1);
  }
  int chosenAlgorithm = atoi(argv[1]);
  for (int i = 1; i <= 15; i++) {
    int numberOfVertices = pow(2, i);
    cout << "k = " << i << "; |V| = " << numberOfVertices << endl;
    createEdges(numberOfVertices);
    cout << "done creating edges" << endl;
    for (int j = 1; j <= numberOfVertices; j++) {
      makeSet(j);
    }
    bool done;
    switch (chosenAlgorithm) {
    case 1:
      done = performNaiveUnionFind(numberOfVertices);
      break;
    case 2:
      done = performLRPC(numberOfVertices);
      break;
    case 3:
      done = performREM(numberOfVertices);
      break;
    case 4:
      done = performSP_REM(numberOfVertices);
      break;
    default:
      cerr << "Error: unknown algorithm << " << chosenAlgorithm << "!" << endl;
      exit(1);
    }
    if (done) {
      cout << "cost of minimal spanning tree: " << totalCost << endl;
    } else {
      cout << "cost of found tree: " << totalCost << "; but somehow not done...: " << spanningTree.size() << " / " << (numberOfVertices - 1) << endl;
      list<pair<int, int> >::iterator it = spanningTree.begin();
      while (it != spanningTree.end()) {
	cout << (*it).first << "->" << (*it).second << endl;
	it++;
      }
      cout << "costs: " << endl;
      for (int j = 1; j <= 10; j++) {
	cout << j << ":";
	for (int k = 0; k < edgeWeights[j].size(); k++) {
	  cout << edgeWeights[j][k].first << "->" << edgeWeights[j][k].second << " ";
	}
	cout << endl;
      }
    }
    cleanup();
  }
  return EXIT_SUCCESS;
}

void createEdges(int numberOfVertices) {
  for (int i = 1; i <= 10; i++) { // initialize weight map
    vector<pair<int, int> > vec;
    edgeWeights[i] = vec;
  }
  srand(time(0)); // initialize the random number generator
  for (int u = 0; u < numberOfVertices; u++) {
    for (int v = u + 1; v < numberOfVertices; v++) {
      pair<int, int> uv(u, v);
      edgeWeights[rand() % 10 + 1].push_back(uv); // set weight for edge u-v
    }
  }
}

void makeSet(int index) {
  vertex* v = new vertex(index);
  sets.push_back(v);
}

bool performNaiveUnionFind(int numberOfVertices) {
  for (int j = 1; j <= 10; j++) {
    for (int k = 0; k < edgeWeights[j].size(); k++) {
      vertex* parentU = sets[edgeWeights[j][k].first]->findNaive();
      vertex* parentV = sets[edgeWeights[j][k].second]->findNaive();
      if (parentU != parentV) {
	if (parentU->rank <= parentV->rank) {
	  parentV->unionNaive(parentU);
	} else {
	  parentU->unionNaive(parentV);
	}
	spanningTree.push_back(edgeWeights[j][k]);
	totalCost += j;
	if (spanningTree.size() == numberOfVertices - 1) {
	  return true;
	}
      }
    }
  }
  return false;
}

bool performLRPC(int numberOfVertices) {
  for (int j = 1; j <= 10; j++) {
    for (int k = 0; k < edgeWeights[j].size(); k++) {
      vertex* parentU = sets[edgeWeights[j][k].first]->findPathCompression();
      vertex* parentV = sets[edgeWeights[j][k].second]->findPathCompression();
      if (parentU != parentV) {
	if (parentU->rank <= parentV->rank) {
	  parentV->unionLinkByRank(parentU);
	} else {
	  parentU->unionLinkByRank(parentV);
	}
	spanningTree.push_back(edgeWeights[j][k]);
	totalCost += j;
	if (spanningTree.size() == numberOfVertices - 1) {
	  return true;
	}
      }
    }
  }
  return false;
}

bool performREM(int numberOfVertices) {
  for (int j = 1; j <= 10; j++) {
    for (int k = 0; k < edgeWeights[j].size(); k++) {
      if (sets[edgeWeights[j][k].first]->rem(sets[edgeWeights[j][k].second])) { // two sets merged
	spanningTree.push_back(edgeWeights[j][k]);
	totalCost += j;
	if (spanningTree.size() == numberOfVertices - 1) {
	  return true;
	}
      }
    }
  }
  return false;
}

bool performSP_REM(int numberOfVertices) {
  for (int j = 1; j <= 10; j++) {
    for (int k = 0; k < edgeWeights[j].size(); k++) {
      if (sets[edgeWeights[j][k].first]->sp_rem(sets[edgeWeights[j][k].second])) { // two sets merged
	spanningTree.push_back(edgeWeights[j][k]);
	totalCost += j;
	if (spanningTree.size() == numberOfVertices - 1) {
	  return true;
	}
      }
    }
  }
  return false;
}

void cleanup() {
  totalCost = 0;
  spanningTree.clear();
  sets.clear();
  for (int j = 1; j <= 10; j++) {
    edgeWeights[j].clear();
  }
}