biconnect_p_ur.cpp

来自「C++语言下, 关于图论算法的一些模版, 包括一般图最大匹配, km匹配, 最小」· C++ 代码 · 共 52 行

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

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[N], 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], brkc = g[c][cur[c]];
		if(dfn[c] == -1) { low[c] = dfn[c] = cnt++; brkc = -1; est[etop++] = c; }
		for(; cur[c] >= 0; cur[c]--) {
			int no = g[c][cur[c]];
			if(no == cp) continue;
			if(dfn[no] != -1) {
				if(brkc == no) {
					if(low[no] >= dfn[c]) {
						int u; bc[bcnt].clear();
						do {
							u = est[--etop];
							bc[bcnt].push_back(u);
						} while(u != no);
						bc[bcnt].push_back(c); bcnt++;
					}
					low[c] <?= low[no];
				} else low[c] <?= dfn[no];
			} else {
				stack[top++] = no; pst[ptop++] = c; break;
			}
		}
		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);
}