This is a demo for Karger's algorithm for graph min cut inspired by [Geeksforgeeks](http://www.geeksforgeeks.org/kargers-algorithm-for-minimum-cut-set-1-introduction-and-implementation/) and [Coursera: Algorithm design and analysis by Stanford University](https://www.coursera.org/learn/algorithm-design-analysis/home/week/3)

Karger_mincut_demo.cpp

#include <iostream>
#include <vector>
#include <fstream>
#include <iterator>
#include <string>
#include <set>
#include <cstdlib>
#include <ctime>
#include <sstream>      // std::istringstream
#include <map>
using namespace std;

class UnionFind {
protected:
	vector<int> id_;   // id_[i] = root(i)
	vector<int> sz_;   // sz_[i] = number of sons and grand-sons whose root is i
	int cnt_;          // count of the components
	int find(int p);
public:
	explicit UnionFind(int size);

	inline int getSize()const {
		return id_.size();
	}

	inline bool connected(int p, int q) {
		return find(p) == find(q);
	}

	void unionTwo(int p, int q);
};
UnionFind::UnionFind(int size):cnt_(size) {
	id_.reserve(size);
	sz_.reserve(size);
	for(int i = 0; i < size; ++i) {
		id_.push_back(i);
		sz_.push_back(1);
	}
}

int UnionFind::find(int p) {
	while(p != id_[p]) {
		p = id_[p];
	}
	return p;
}

void UnionFind::unionTwo(int p, int q) {
	int i = find(p);
	int j = find(q);
	if(i == j)	return;   // they have unioned
	if(sz_[i] < sz_[j]) {
		id_[i] = j;
		sz_[j] += sz_[i];
	} else {
		id_[j] = id_[i];
		sz_[i] += sz_[j];
	}
	--cnt_;
}

class Graph {
private:
	vector<pair<int, int>> edges;
	set<int> vertices;
public:
	void addEdge(int start, int end);
	int getEdgeNumber() const {
		return edges.size();
	}
	int getVerticeNumber() const {
		return vertices.size();
	}

	const vector<pair<int, int>>& getEdges() const {
		return edges;
	}
};

void Graph::addEdge(int start, int end) {
	vertices.insert(start);
	vertices.insert(end);
	edges.push_back(pair<int, int>{start, end});
}


int minCut(const Graph& g) {
	int n_e = g.getEdgeNumber();
	int n_v = g.getVerticeNumber();
	UnionFind uf(n_v);
	while(n_v > 2) {
		//1. 随机选取两个不在一个subset的顶点组成的边
		int choosen = rand() % n_e;
		int start = g.getEdges()[choosen].first;
		int end = g.getEdges()[choosen].second;
		if(uf.connected(start, end)) continue;
		//cout << "Contrast vertice " << start << " and " << end << "\n";
		n_v--;
		uf.unionTwo(start, end);
	}
	int cnt = 0;
	for(const auto& p : g.getEdges()) {
		if(!uf.connected(p.first, p.second)) ++cnt;
	}
	return cnt;
}


int main(int argc, char** argv) {
	ifstream fin("MinCut.txt", ios::in);
	string str;

	Graph graph;
	while(getline(fin, str)) {
		istringstream buffer(str);
		vector<int> line((istream_iterator<int>(buffer)), istream_iterator<int>());
		int vertice = line[0];
		for(int i = 1; i < line.size(); ++i) {
			if(vertice >= line[i])	continue;
			graph.addEdge(vertice-1, line[i] - 1);
		}
	}
	cout << "Edge number: " << graph.getEdgeNumber() << "\n";
	cout << "Vertice number: " << graph.getVerticeNumber() << "\n";
	srand(time(NULL));
	int min_cut = INT_MAX;
	for(int i = 0; i < 100; ++i) {
		int cut = minCut(graph);
		if(min_cut > cut) min_cut = cut;
		
	}
	cout << min_cut << endl;
	return 0;
}