# include <iostream>
# include <climits>
# include <cstdlib>
# include <ctime>
# include <cmath>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

class UnionFind {
	private:
		int* set;
	public:
		UnionFind(int n){ //kazdy wierzcholek jest osobnym drzewem
			set = new int[n];
			for(int i=0;i<n;i++) set[i] = i;
		}
		~UnionFind();
		int FindSet(int e){ //usyawiamy nazwe, ktora jest zawsze najmniejszy element
			if (set[e] != e) set[e] = FindSet(set[e]);
			return set[e];
		}
		void Union(int x, int y){//laczymy x oraz y
			int x_root = FindSet(x);
			int y_root = FindSet(y);
			if (x_root<y_root) set[y_root] = x_root;//ustawiamy nazwe po polaczeniu
			else set[x_root] = y_root;
		}
};

class Edge { //tworzymy klase krawedz
	public:
		int start;
		int end;
		float value;
		Edge(int s, int e, float w){//polaczone wierzcholki to s i e, w to waga
			start = s;
			end = e;
			value = w;
		}
		inline bool operator<(const Edge &s) const {return value < s.value;} //definiujemy operatory <,>,==,by móc porównywac elementy edge

		inline bool operator>(const Edge &s) const {return value > s.value;}

		inline bool operator==(const Edge &s) const {return value == s.value;}
};
void print_edges(vector<Edge> list){
	int size = list.size(); //zwraca liczbe elementow znajdujacych sie aktualnie w kontenerze(zwraca rozmiar listy)
	for (int i=0;i<size;i++)
		cout<<"["<<list[i].start<<","<<list[i].end<<","<<list[i].value<<"]"<<endl; //daje początek, koniec i wartosc krawedzi
}
vector<Edge> generuj_graf(int ilosc, int pro, float max){ //ilosc  //graf losowy //pro-to nasze prawdopodobienstwo
	vector<Edge> l;
	l.clear(); //pusty kontener
	for(int i=0;i<ilosc;i++)
		for(int j=i+1;j<ilosc;j++){
			int a=rand();
			if (a<pro){
				float val = rand()/max;
				l.push_back(Edge(i,j,val)); //dodajemy nowy element na koniec kontenera
			}
		}
	sort(l.begin(),l.end()); //sortujemy od początku do końca
	return l;                     //zwracamy krawedz
}

int main(){
	cout<<"RAND_MAX:"<<RAND_MAX<<endl; //maksymalna wartosc jaka moze byc zwrocona przez rand
	srand(time(0)); //za kazdym razem zarodek liczb pseudolosowy jest inny
	clock_t t1 = clock();
	vector<Edge> l;
	float max = float(RAND_MAX);
 	for(int k=1;k<=9;k++){
		cout<<"k:"<<k<<endl;
		int counter = 0;
		int nbr_of_nodes = 1<<k; //liczba wierzcholkow
		int pro =  (RAND_MAX/(1<<k))*k;
		float global_values = 0;
		for (int i=0;i<1000;i++){
			l.clear();
			UnionFind* graph = new UnionFind(nbr_of_nodes);
			l = generuj_graf(nbr_of_nodes, pro, max);
			int unions = 0, size = l.size();
			float values = 0;
			for(int x=0;x<size;x++){
				Edge current_edge = l[x];
				int first_set = graph->FindSet(current_edge.start);
				int second_set = graph->FindSet(current_edge.end);
				if (first_set != second_set){
					graph->Union(first_set, second_set);
					unions++;
					values += current_edge.value; //suma wag
				}
				if (unions==nbr_of_nodes-1){
					counter++;
					global_values += values;
					break;
				}
			}
		}
		float per=(counter/float(1000))*100; //procent spójnych grafow
		cout<<"Ilosc spojnych grafow: "<<per<<"%"<<endl;
		cout<<"Srednia waga drzewa dla spojnych grafow: "<<global_values/counter<<endl;
	}
	clock_t t2 = clock();
	float diff ((float)t2-(float)t1);
    cout<<diff / CLOCKS_PER_SEC<<"sekund"<<endl;
	return 0;
}