Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- const int nax = 1e5 + 2;
- vector<int>tree[nax * 2];
- int n, m;
- int sub[nax * 2];
- long long ans = 0;
- void ad(int u, int v) {
- tree[u].push_back(v);
- tree[v].push_back(u);
- }
- template<int SZ> struct BCC {
- vector<int>adj[SZ];
- int N;
- int pre_order[SZ], low[SZ], par[SZ];
- int compsz[SZ];
- int ti = 0;
- vector<pair<int,int>>st;
- vector<vector<pair<int,int>>>fin;
- void addEdge(int u, int v) {
- adj[u].push_back(v);
- adj[v].push_back(u);
- }
- void BCCutil(int u, bool root = 0) {
- pre_order[u] = low[u] = ti++;
- int child = 0;
- for(int i : adj[u]) if(i!=par[u]) {
- if(pre_order[i]==-1) {
- ++child, par[i] = u;
- st.emplace_back(u, i);
- BCCutil(i);
- low[u] = min(low[u], low[i]);
- if((root && child>1) || (!root && low[i]>=pre_order[u])) {// cut vertex
- int l = fin.size();
- fin.emplace_back();
- while(1) {
- fin[l].push_back(st.back());
- st.pop_back();
- if(fin[l].back()==make_pair(u, i)) break;
- }
- }
- } else if(pre_order[i] < pre_order[u]) {
- low[u] = min(low[u], pre_order[i]);
- st.emplace_back(u, i);
- }
- }
- }
- void bcc() {
- for(int i=1; i<=N; ++i) {
- pre_order[i] = par[i] = low[i] = -1;
- }
- for(int i=1; i<=N; ++i) {
- if(pre_order[i]==-1) {
- BCCutil(i, 1);
- if(!st.empty()) fin.push_back(st);
- st.clear();
- }
- }
- int co = 0;
- for(auto a : fin) {
- set<int>s;
- for(auto b : a) {
- s.insert(b.first), s.insert(b.second);
- }
- ++co;
- compsz[co] = s.size();
- for(int i : s) ad(i, co+N);
- }
- }
- };
- BCC<nax>a;
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
