#include "graph_tree/two_edge_connectivity.hpp"
#include<vector> #include<stack> #include<algorithm> #include"graph_template.hpp" /** * @brief 二辺連結成分分解 */ struct two_edge_connectivity{ std::vector<int>order,cmp; std::stack<int> s,roots; std::vector<bool> ins; std::vector<std::vector<int>>each_bcc; std::vector<std::pair<int,int>>brige; two_edge_connectivity(graph g){ int n=g.size(); order.resize(n,0); ins.resize(n,0); cmp.resize(n); for(int i=0;i<n;i++){ if(!order[i])dfs(g,i,-1); } } void dfs(const graph& g,int v,int p){ order[v]=(p==-1?0:order[p])+1; s.emplace(v); ins[v]=1; roots.emplace(v); bool f=1; for(auto e:g[v]){ if(e==p&&f){f=0;continue;} if(!order[e])dfs(g,e,v); else if(e!=v&&ins[e])while(order[roots.top()]>order[e])roots.pop(); } if(v==roots.top()){ if(p!=-1)brige.push_back(std::minmax(p,v)); std::vector<int>bcc; while(1){ int e=s.top();s.pop();ins[e]=0; bcc.push_back(e); cmp[v]=each_bcc.size(); if(e==v)break; } each_bcc.push_back(bcc); roots.pop(); } } auto get_bcc(){return each_bcc;} auto get_v(){return cmp;} auto get_brige(){return brige;} };
#line 1 "graph_tree/two_edge_connectivity.hpp" #include<vector> #include<stack> #include<algorithm> #line 3 "graph_tree/graph_template.hpp" #include<tuple> #include<iostream> /** * @brief グラフテンプレート */ using graph=std::vector<std::vector<int>>; template<typename T> using graph_w=std::vector<std::vector<std::pair<int,T>>>; graph load_graph(int n,int m){graph g(n);for(int i=0;i<m;++i){int s,t;std::cin>>s>>t;--s;--t;g[s].push_back(t);g[t].push_back(s);}return g;} graph load_digraph(int n,int m){graph g(n);for(int i=0;i<m;++i){int s,t;std::cin>>s>>t;--s;--t;g[s].push_back(t);}return g;} graph load_graph0(int n,int m){graph g(n);for(int i=0;i<m;++i){int s,t;std::cin>>s>>t;g[s].push_back(t);g[t].push_back(s);}return g;} graph load_digraph0(int n,int m){graph g(n);for(int i=0;i<m;++i){int s,t;std::cin>>s>>t;g[s].push_back(t);}return g;} graph load_tree(int n){graph g(n);for(int i=0;i<n-1;++i){int s,t;std::cin>>s>>t;--s;--t;g[s].push_back(t);g[t].push_back(s);}return g;} graph load_tree0(int n){graph g(n);for(int i=0;i<n-1;++i){int s,t;std::cin>>s>>t;g[s].push_back(t);g[t].push_back(s);}return g;} graph load_treep(int n){graph g(n);for(int i=0;i<n-1;++i){int t;std::cin>>t;g[i+1].push_back(t);g[t].push_back(i+1);}return g;} template<typename T>graph_w<T> load_graph_weight(int n,int m){graph_w<T> g(n);for(int i=0;i<m;++i){int s,t;T u;std::cin>>s>>t>>u;--s;--t;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;} template<typename T>graph_w<T> load_digraph_weight(int n,int m){graph_w<T> g(n);for(int i=0;i<m;++i){int s,t;T u;std::cin>>s>>t>>u;--s;--t;g[s].emplace_back(t,u);}return g;} template<typename T>graph_w<T> load_graph0_weight(int n,int m){graph_w<T> g(n);for(int i=0;i<m;++i){int s,t;T u;std::cin>>s>>t>>u;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;} template<typename T>graph_w<T> load_digraph0_weight(int n,int m){graph_w<T> g(n);for(int i=0;i<m;++i){int s,t;T u;std::cin>>s>>t>>u;g[s].emplace_back(t,u);}return g;} template<typename T>graph_w<T> load_tree_weight(int n){graph_w<T> g(n);for(int i=0;i<n-1;++i){int s,t;T u;std::cin>>s>>t>>u;--s;--t;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;} template<typename T>graph_w<T> load_tree0_weight(int n){graph_w<T> g(n);for(int i=0;i<n-1;++i){int s,t;T u;std::cin>>s>>t>>u;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;} template<typename T>graph_w<T> load_treep_weight(int n){graph_w<T> g(n);for(int i=0;i<n-1;++i){int t;T u;std::cin>>t>>u;g[i+1].emplace_back(t,u);g[t].emplace_back(i+1,u);}return g;} #line 5 "graph_tree/two_edge_connectivity.hpp" /** * @brief 二辺連結成分分解 */ struct two_edge_connectivity{ std::vector<int>order,cmp; std::stack<int> s,roots; std::vector<bool> ins; std::vector<std::vector<int>>each_bcc; std::vector<std::pair<int,int>>brige; two_edge_connectivity(graph g){ int n=g.size(); order.resize(n,0); ins.resize(n,0); cmp.resize(n); for(int i=0;i<n;i++){ if(!order[i])dfs(g,i,-1); } } void dfs(const graph& g,int v,int p){ order[v]=(p==-1?0:order[p])+1; s.emplace(v); ins[v]=1; roots.emplace(v); bool f=1; for(auto e:g[v]){ if(e==p&&f){f=0;continue;} if(!order[e])dfs(g,e,v); else if(e!=v&&ins[e])while(order[roots.top()]>order[e])roots.pop(); } if(v==roots.top()){ if(p!=-1)brige.push_back(std::minmax(p,v)); std::vector<int>bcc; while(1){ int e=s.top();s.pop();ins[e]=0; bcc.push_back(e); cmp[v]=each_bcc.size(); if(e==v)break; } each_bcc.push_back(bcc); roots.pop(); } } auto get_bcc(){return each_bcc;} auto get_v(){return cmp;} auto get_brige(){return brige;} };