strconnect_ur.cpp

C++语言下, 关于图论算法的一些模版, 包括一般图最大匹配, km匹配, 最小割等等, 共15个模版

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
const int N = 256;

class Graph {
private:
	vector<int> g[N];
	int n, m, h[N], id[N];
	int cnt, scnt, dfn[N], low[N], cur[N];
	int stack[N], top, est[N], etop;
	void dfs(int);
public:
	void scR();
};
void Graph::scR() {
	memset(dfn, -1, sizeof(dfn));
	cnt = scnt = 0;
	for(int i = 0; i < n; i++) cur[i] = g[i].size()-1;
	for(int i = 0; i < n; i++)
		if(dfn[i] == -1) dfs(i);
}
void Graph::dfs(int src) {
	etop = top = 0;
	stack[top++] = src;
	while(top != 0) {
		int	c = stack[top-1];
		if(dfn[c] == -1) { h[c] = dfn[c] = low[c] = cnt++; est[etop++] = c; }
		for(; cur[c] >= 0; cur[c]--) {
			int no = g[c][cur[c]];
			if(dfn[no] == -1) { stack[top++] = no; break; }
			h[c] <?= low[no];
		}
		if(cur[c] >= 0) continue;
		top--; int k;
		if(h[c] != low[c]) { low[c] = h[c]; continue; }
		do {
			k = est[--etop];
			id[k] = scnt; low[k] = N;
		} while(k != c);
		scnt++;
	}
}