biconnect_e_ur.cpp

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

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
const int N = 320000;
const int E = 1 << 20;

class Graph {
public:
	vector<int> g[N], bc[N];
	int n, dfn[N], low[N], cur[N], cnt, bcnt;
	int stack[N], top, pst[N], ptop, est[E], etop;
	void dfs(int);
public:
	void bcR();
};
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++;
		for(; cur[c] >= 0; cur[c]--) {
			int no = g[c][cur[c]];
			if(no == cp) continue;
			if(dfn[no] != -1) {
				if(dfn[no] < dfn[c]) { stack[top++] = c; stack[top++] = no; }
				low[c] <?= dfn[no];
			} else {
				est[etop++] = c; est[etop++] = no;
				stack[top++] = no; pst[ptop++] = c; break;
				if(low[no] >= dfn[c]) {
					int u, v; bc[bcnt].clear();
					do {
						v = stack[--top]; u = stack[--top];
						bc[bcnt].push_back(u); bc[bcnt].push_back(v);
					} while(u != c || v != no);
					bcnt++;
				}
				low[c] <?= low[no];
			}
		}
		if(cur[c] < 0) { top--; ptop--; }
	}
}
void Graph::bcR() {
	memset(dfn, -1, sizeof(dfn));
	cnt = bcnt = 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);
}