biconnect_br_ur.cpp

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

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

class Graph {
private:
	vector<int> g[N];
	int n, bcnt, cnt, dfn[N], cur[N], low[N], pcnt[N];
	int id[N], d[N];
	int stack[N], top, pst[N], ptop, est[N], etop;
	void dfs(int);
public:
	void brcR();
};
void Graph::dfs(int src) {
	etop = ptop = top = 0;
	stack[top++] = src; pst[ptop++] = -1;
	while(top != 0) {
		int	c = stack[top-1], cp = pst[ptop-1];
		if(dfn[c] == -1) { low[c] = dfn[c] = cnt++; est[etop++] = c; }
		for(; cur[c] >= 0; cur[c]--) {
			int no = g[c][cur[c]];
			if(no == cp) { pcnt[c]++; continue; }
			if(dfn[no] == -1) { stack[top++] = no; pst[ptop++] = c; break; }
			if(dfn[no] < dfn[c]) low[c] <?= dfn[no];
			else low[c] <?= low[no];
		}
		if(cur[c] >= 0) continue;
		top--; ptop--;
		if(pcnt[c] > 1) low[c] <?= dfn[cp];
		if(low[c] == dfn[c]) {
			int k;
			do {
				k = est[--etop];
				id[k] = bcnt;
			} while(k != c);
			bcnt++;
		}
	}
}
void Graph::brcR() {
	bcnt = cnt = top = 0;
	memset(dfn, -1, sizeof(dfn)); memset(pcnt, 0, sizeof(pcnt));
	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(0);
}