Lowlink
二重点連結成分分解...?
bc_id[辺のid]でその辺がどの連結成分に含まれているかを返していそう...?
code:cpp
struct Lowlink {
struct Edge {
int to, id;
Edge() {}
Edge(int to, int id=-1): to(to), id(id) {}
};
int n, m;
vector<vector<Edge>> g;
vector<pair<int,int>> edges;
Lowlink(int n): n(n), m(0), g(n) {}
void addEdge(int a, int b) {
if (a > b) swap(a,b);
edges.emplace_back(a,b);
}
vector<int> ord, low, par;
void init() {
ord = low = par = vector<int>(n,-1);
int k = 0;
auto dfs = &(auto dfs, int v, int ei=-1) -> int { for (auto e : gv) if (e.id != ei) { lowv = min(lowv, dfs(dfs, e.to, e.id)); } else if (orde.to < ordv) { }
}
};
rep(v,n) if (ordv == -1) dfs(dfs,v); }
vector<vector<int>> bc;
vector<int> bc_id;
void bcc() { // Bi-Connected-Components
bc_id = vector<int>(m,-1);
auto add = &(int ei, int k) { };
auto dfs = &(auto dfs, int v, int k=-1) -> void { for (auto e : gv) if (e.to != parv) { int nk = k;
if (lowe.to >= ordv) nk = bc.size(), bc.emplace_back(); add(e.id, nk);
dfs(dfs, e.to, nk);
} else if (orde.to < ordv) { add(e.id, k);
}
}
};
for(int v = 0;v<n;v++) if (parv == -1) dfs(dfs, v); /*
rep(i,m) {
printf("%d %d-%d: %d\n", i, a, b, bc_idi); }
rep(v,n) {
printf("%d: %d %d\n", v, ordv, lowv); }//*/
}
};