1 files changed, 53 insertions, 0 deletions
diff --git a/graph/stoerWagner.cpp b/graph/stoerWagner.cpp
new file mode 100644
index 0000000..899cb3b
--- /dev/null
+++ b/graph/stoerWagner.cpp
@@ -0,0 +1,53 @@
+struct edge {
+	int from, to;
+	ll cap;
+};
+
+vector<vector<edge>> adjlist, tmp;
+vector<bool> erased;
+
+void merge(int a, int b) {
+	tmp[a].insert(tmp[a].end(), all(tmp[b]));
+	tmp[b].clear();
+	erased[b] = true;
+	for (auto& v : tmp) {
+		for (auto&e : v) {
+			if (e.from == b) e.from = a;
+			if (e.to == b) e.to = a;
+}}}
+
+ll stoer_wagner() {
+	ll res = INF;
+	tmp = adjlist;
+	erased.assign(sz(tmp), false);
+	for (int i = 1; i < sz(tmp); i++) {
+		int s = 0;
+		while (erased[s]) s++;
+		priority_queue<pair<ll, int>> pq;
+		pq.push({0, s});
+		vector<ll> con(sz(tmp));
+		ll cur = 0;
+		vector<pair<ll, int>> state;
+		while (!pq.empty()) {
+			int c = pq.top().second;
+			pq.pop();
+			if (con[c] < 0) continue; //already seen
+			con[c] = -1;
+			for (auto e : tmp[c]) {
+				if (con[e.to] >= 0) {//add edge to cut
+					con[e.to] += e.cap;
+					pq.push({con[e.to], e.to});
+					cur += e.cap;
+				} else if (e.to != c) {//remove edge from cut
+					cur -= e.cap;
+			}}
+			state.push_back({cur, c});
+		}
+		int t = state.back().second;
+		state.pop_back();
+		if (state.empty()) return 0; //graph is not connected?!
+		merge(state.back().second, t);
+		res = min(res, state.back().first);
+	}
+	return res;
+}