Create a gist now

Instantly share code, notes, and snippets.

@yurahuna /bicc_edge.cpp Secret
Last active Jul 24, 2016

What would you like to do?
typedef vector<vector<int>> Graph;
typedef pair<int, int> Edge; // (a < b: 無向辺)
class BICC {
private:
const int n;
/*** 橋の列挙 ***/
Graph G;
vi depth;
vi par;
map<Edge, int> imosEdge;
map<Edge, int> EdgeType;
enum {UNUSED, USED_DFS, BRIDGE};
vector<Edge> bridges;
/*** 二重辺連結成分 ***/
vi cmp; // cmp[i] = 頂点 i がどの二重辺連結成分に属するか
int num_cc; // 二重辺連結成分の個数
vi size_of_vertex; // 各二重辺連結成分に含まれる頂点の個数
Graph G_cc; // 各二重辺連結成分を頂点とする無向グラフ (!!!木になる!!!)
public:
BICC(int _n) : n(_n), G(_n), depth(_n, -1), par(_n, -1), cmp(_n, -1), num_cc(0) {}
Edge getEdge(int a, int b) {
if (a > b) swap(a, b);
return Edge(a, b);
}
void updateEdgeType(int a, int b, int type) {
if (a < 0 || b < 0) return; // dfsで-1が与えられるとき用
EdgeType[getEdge(a, b)] = type;
}
void addEdge(int a, int b) {
G[a].emplace_back(b);
G[b].emplace_back(a);
updateEdgeType(a, b, UNUSED);
}
void dfsTreeConstruct(int v, int pre) {
if (depth[v] != -1) return;
depth[v] = (pre == -1 ? 0 : depth[pre] + 1);
par[v] = pre;
updateEdgeType(pre, v, USED_DFS);
for (auto&& nxt : G[v]) {
if (nxt != pre) dfsTreeConstruct(nxt, v);
}
}
void updateImos(int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
// depth[a] > depth[b]: DFSで使われなかった a->b の辺
if (par[a] != -1) {
imosEdge[getEdge(a, par[a])]++;
}
if (par[b] != -1) {
imosEdge[getEdge(b, par[b])]--;
}
}
int imosFinal(int v, int pre) {
int t = 0;
for (auto&& nxt : G[v]) {
if (nxt != pre && EdgeType[getEdge(nxt, v)] == USED_DFS) {
t += imosFinal(nxt, v);
}
}
if (pre != -1) imosEdge[getEdge(v, pre)] += t;
return pre == -1 ? 0 : imosEdge[getEdge(v, pre)];
}
// 1つの連結成分を取り出し、その連結成分の大きさを返す
int extractCC(int v, int color) {
if (cmp[v] != -1) return 0;
cmp[v] = color;
int t = 1;
for (auto&& nxt : G[v]) {
if (EdgeType[getEdge(v, nxt)] != BRIDGE) {
t += extractCC(nxt, color);
}
}
return t;
}
void bicc() {
/*** 橋の列挙 ***/
dfsTreeConstruct(0, -1);
for (auto&& p : EdgeType) {
Edge e;
int type;
tie(e, type) = p;
if (type == UNUSED) {
updateImos(e.first, e.second);
}
}
imosFinal(0, -1);
for (auto&& p : EdgeType) {
Edge e;
int type;
tie(e, type) = p;
if (type == USED_DFS) {
if (imosEdge[e] == 0) {
EdgeType[e] = BRIDGE;
bridges.emplace_back(e);
}
}
}
/*** 二重辺連結成分 ***/
rep(i, n) {
int size_cc = extractCC(i, num_cc);
if (size_cc > 0) {
size_of_vertex.emplace_back(size_cc);
num_cc++;
}
}
// cerr << "num_cc = " << num_cc << endl;
// cerr << "cmp: "; printV(cmp);
// cerr << "size_of_vertex: "; printV(size_of_vertex);
vector<set<int>> G_cc_st(num_cc); // 頂点の重複を除くためまずsetでつくる
for (auto&& p : EdgeType) {
Edge e;
int type;
tie(e, type) = p;
if (type == BRIDGE) {
// cerr << e.first << " " << e.second << " " << imosEdge[e] << endl;
G_cc_st[cmp[e.first]].insert(cmp[e.second]);
G_cc_st[cmp[e.second]].insert(cmp[e.first]);
}
}
rep(i, num_cc) {
G_cc.emplace_back(vector<int>(all(G_cc_st[i])));
}
// cerr << "---BICC---" << endl;
// rep(i, num_cc) {
// cerr << i << ": "; printV(G_cc[i]);
// }
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment