// GraphTask.cpp : Этот файл содержит функцию "main". Здесь начинается и заканчивается выполнение программы.
//

#include "pch.h"
#define _CRT_SECURE_NO_DEPRECATE
#include <fstream>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>

using namespace std;


struct ThreeVertices
{
	int first, second, third;
	ThreeVertices(int x, int y, int z)
	{
		first = x;
		second = y;
		third = z;
	}
};

class BipartiteGraph
{
private:
	int verticesCount;
	int secondSetStart;
	vector<set<int>> edges;

	BipartiteGraph(vector<set<int>> _edges, int _verticesCount, int _secondSetStart)
	{
		edges = _edges;
		verticesCount = _verticesCount;
		secondSetStart = _secondSetStart;
	}

public:
	BipartiteGraph(int _verticesCount, int _secondSetStart)
	{
		edges = vector<set<int>>(_verticesCount);
		verticesCount = _verticesCount;
		secondSetStart = _secondSetStart;
	}

	int GetVerticesSize()
	{
		return verticesCount;
	}

	int GetTheSecondSetStart()
	{
		return secondSetStart;
	}

	int GetEdgeCountForOneVertex(int vertexNumber)
	{
		return edges[vertexNumber].size();
	}

	vector <set<int>> GetEges()
	{
		return edges;
	}

	BipartiteGraph Copy()
	{
		return BipartiteGraph(edges, verticesCount, secondSetStart);
	}

	bool ContainsEdge(const int firstVertex, int secondVertex)
	{
		return edges[firstVertex].find(secondVertex) != edges[firstVertex].end();;
	}

	void AddEdge(int from, int to)
	{
		// add edge from 'from' to 'to'
		edges[from].insert(to);
		edges[to].insert(from);
	}

	void RemoveEdge(int from, int to)
	{
		// remove edge from 'from' to 'to'
		/*auto itemTo = find(edges[from].begin(), edges[from].end(), to);
		if (itemTo != edges[from].end())
		{
			edges[from].erase(itemTo);
		}
		auto itemFor = find(edges[from].begin(), edges[from].end(), to);
		if (itemFor != edges[from].end())
		{
			edges[from].erase(itemFor);
		}*/

		edges[from].erase(to);
		edges[to].erase(from);
	}

	void Print()
	{
		cout << "Vertices " << verticesCount << " " << "Second Start " << secondSetStart << endl;
		for (int i = 0; i < secondSetStart; ++i)
		{
			std::set<int>::iterator it;
			for (it = edges[i].begin(); it != edges[i].end(); ++it)
			{
				cout << "From " << i << " " << "To " << *it << endl;
			}

		}
	}

	int GetSecondSetStart()
	{
		return secondSetStart;
	}

	int GetVertexDegree(int vertexIndex)
	{
		return edges[vertexIndex].size();
	}

	int GetEdgeSetSize()
	{
		return edges.size();
	}

	void FindIncreasingVertices(vector<ThreeVertices>& increasingVertices)
	{
		for (int i = 0; i < edges.size(); ++i)
		{
			std::set<int>::iterator it;
			for (it = edges[i].begin(); it != edges[i].end(); ++it)
			{
				if (i > *it)
				{
					continue;
				}
				int firstSetVertex = i;
				int secondSetVertex = *it;

				for (int j = 0; j < secondSetStart; ++j)
				{
					if (firstSetVertex == j)
					{
						continue;
					}

					if (!ContainsEdge(secondSetVertex, j))
					{
						if (GetVertexDegree(firstSetVertex) <= GetVertexDegree(j))
						{
							increasingVertices.push_back(ThreeVertices(firstSetVertex, secondSetVertex, j));
						}
					}
				}

				for (int e = secondSetStart; e < verticesCount; ++e)
				{
					if (e == secondSetVertex)
					{
						continue;
					}

					if (!ContainsEdge(e, firstSetVertex))
					{
						if (GetVertexDegree(secondSetVertex) <= GetVertexDegree(e))
						{
							increasingVertices.push_back(ThreeVertices(secondSetVertex, firstSetVertex, e));
						}
					}
				}
			}
		}
	}

};

void ApplyRotation(BipartiteGraph & graph, ThreeVertices vertices)
{
	// удалить одно ребро и добавить другое
	graph.RemoveEdge(vertices.first, vertices.second);
	graph.AddEdge(vertices.second, vertices.third);
}

void RollbackRotation(BipartiteGraph & graph, ThreeVertices vertices)
{
	// удалить одно ребро и добавить другое
	graph.RemoveEdge(vertices.second, vertices.third);
	graph.AddEdge(vertices.first, vertices.second);
}


void GenerateAllGraphs(BipartiteGraph& graph, vector<BipartiteGraph> & resultGraphs, int level)
{
	vector<ThreeVertices> increasingVertices;
	graph.FindIncreasingVertices(increasingVertices);

	if (increasingVertices.empty())
	{
		auto graphCopy = graph.Copy();
		resultGraphs.push_back(graphCopy);
		return;
	}

	if (level == 0) {
		printf("Found increasing triples: %d\n", static_cast<int>(increasingVertices.size()));
	}

	for (int x = 0; x < increasingVertices.size(); ++x)
	{
		if (level == 0) {
			printf("%d\n", x);
		}
		ApplyRotation(graph, increasingVertices[x]);
		GenerateAllGraphs(graph, resultGraphs, level + 1);
		RollbackRotation(graph, increasingVertices[x]);
	}
}

bool AreGraphsEqual(BipartiteGraph & firstGraph, BipartiteGraph & secondGraph)
{
	int edgeSetSize = firstGraph.GetEdgeSetSize();

	vector<int> firstGraphDegrees(edgeSetSize);
	vector<int> secondGraphDegrees(edgeSetSize);

	for (int j = 0; j < edgeSetSize; ++j)
	{
		firstGraphDegrees[j] = firstGraph.GetVertexDegree(j);
		secondGraphDegrees[j] = secondGraph.GetVertexDegree(j);
	}
	sort(firstGraphDegrees.begin(), firstGraphDegrees.end());
	sort(secondGraphDegrees.begin(), secondGraphDegrees.end());

	return equal(firstGraphDegrees.begin(), firstGraphDegrees.end(), secondGraphDegrees.begin());
}

void SelectUniqueGraphs(vector<BipartiteGraph> & allGraphs, vector<BipartiteGraph> & uniqueGraphs)
{
	for (int x = 0; x < allGraphs.size(); ++x)
	{
		bool flag = true;
		for (int y = x+1; y < allGraphs.size(); ++y)
		{
			if (AreGraphsEqual(allGraphs[x], allGraphs[y]))
			{
				flag = false;
				break;
			}

		}
		if (flag)
		{
			uniqueGraphs.push_back(allGraphs[x]);
		}
	}
}

BipartiteGraph ReadGraph(string fileName)
{
	ifstream myfile;
	myfile.open(fileName);

	int verticesCount, edgesCount;
	myfile >> verticesCount >> edgesCount;

	vector<set<int>> edgesPaths(edgesCount);
	int secondSetStart;
	myfile >> secondSetStart;

	BipartiteGraph readGraph = BipartiteGraph(verticesCount, secondSetStart);

	for (int i = 0; i < edgesCount; ++i)
	{
		int to, from;
		myfile >> from;
		myfile >> to;

		readGraph.AddEdge(from, to);
	}

	return readGraph;
}

void PrintResult(vector<BipartiteGraph> & resultGraphs)
{
	for (int i = 0; i < resultGraphs.size(); ++i)
	{
		resultGraphs[i].Print();
	}
}

BipartiteGraph GenerateGraph(double edgeProbability, int verticesCount)
{
	int secondSetStart = verticesCount / 2;

	BipartiteGraph generatedGraph = BipartiteGraph(verticesCount, secondSetStart);

	for (int i = 0; i < secondSetStart; ++i)
	{
		for (int j = secondSetStart; j < verticesCount; ++j)
		{
			double randomNumb = (double)rand() / RAND_MAX;
			if (randomNumb <= edgeProbability)
			{
				generatedGraph.AddEdge(i, j);
			}
		}

	}
	return generatedGraph;
}

void WriteGraphToFile(BipartiteGraph graph) {

	FILE * fp = fopen("graph_description", "w");

	int verticesCount = graph.GetVerticesSize();

	fprintf(fp, "%d\n", verticesCount);

	for (int i = 0; i < verticesCount; ++i)
	{
		int edgeCount = graph.GetEdgeCountForOneVertex(i);
		fprintf(fp, "%d ", edgeCount); //для i вершины записываем кол-во вершин, с кот она соединена ребром

		vector <set<int>> edges = graph.GetEges();
		std::set<int>::iterator it;

		for (it = edges[i].begin(); it != edges[i].end(); ++it)
		{
			fprintf(fp, "%d ", *it); // запись самих вершин
		}

		fprintf(fp, "\n");
	}

	int secondSetStart = graph.GetTheSecondSetStart();
	fprintf(fp, "%d", secondSetStart);

	fclose(fp);
}

int main()
{
	const int MAX_VERTICES_COUNT = 20 * 1000;

	double edgeProbability;
	printf("Enter edge probability: \n");
	scanf("%lf", &edgeProbability);

	int verticesCount;
	printf("Enter vertices count: \n");
	scanf("%d", &verticesCount);

	if (verticesCount < 1 || verticesCount > MAX_VERTICES_COUNT) {
		printf("Vertices count must be in interval [1; %d]\n", MAX_VERTICES_COUNT);
		return 0;
	}

	if (edgeProbability < 0 || edgeProbability > 1) {
		printf("Edge probability must be in interval [0; 1]");
		return 0;
	}

	BipartiteGraph generatedGraph = GenerateGraph(edgeProbability, verticesCount);
	WriteGraphToFile(generatedGraph);


	//string fileName = "in.txt";
	//auto generatedGraph = ReadGraph(fileName);


	vector<BipartiteGraph> resultGraphs;
	GenerateAllGraphs(generatedGraph, resultGraphs, 0);

	vector<BipartiteGraph> uniqueGraphs;
	SelectUniqueGraphs(resultGraphs, uniqueGraphs);

	PrintResult(uniqueGraphs);
	cout << uniqueGraphs.size();



	return 0;
}