:warning: 二辺連結成分分解
(graph_tree/two_edge_connectivity.hpp)

Depends on

Code

#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;}
};
Back to top page