#include "graph_tree/scc.hpp"
#pragma once #include<vector> #include<tuple> #include<algorithm> #include"graph_template.hpp" /** * @brief 強連結成分分解 */ std::pair<std::vector<int>,graph> scc(const graph& g){ int n=g.size(); std::vector<std::vector<int>>rev(n); for(int i=0;i<n;i++)for(auto e:g[i]){ rev[e].emplace_back(i); } int idx=0; std::vector<int>v(n,-1); std::vector<bool>visited(n,0); auto dfs=[&](auto dfs,int now)->void{ visited[now]=1; for(auto e:g[now]){ if(!visited[e])dfs(dfs,e); } v[idx++]=now; }; for(int i=0;i<n;i++){ if(!visited[i])dfs(dfs,i); } idx=-1; std::vector<int>res(n,-1); auto rdfs=[&](auto rdfs,int now)->void{ for(auto e:rev[now]){ if(res[e]==-1)res[e]=idx,rdfs(rdfs,e); } }; for(int i=n-1;i>=0;--i){ if(res[v[i]]==-1){ res[v[i]]=++idx; rdfs(rdfs,v[i]); } } idx++; std::vector<std::vector<int>>res2(idx); for(int i=0;i<n;i++)for(auto e:g[i]){ if(res[i]==res[e])continue; res2[res[i]].push_back(res[e]); } for(int i=0;i<idx;i++){ std::sort(res2[i].begin(),res2[i].end()); res2[i].erase(std::unique(res2[i].begin(),res2[i].end()),res2[i].end()); } return {res,res2}; }
#line 2 "graph_tree/scc.hpp" #include<vector> #include<tuple> #include<algorithm> #line 4 "graph_tree/graph_template.hpp" #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 6 "graph_tree/scc.hpp" /** * @brief 強連結成分分解 */ std::pair<std::vector<int>,graph> scc(const graph& g){ int n=g.size(); std::vector<std::vector<int>>rev(n); for(int i=0;i<n;i++)for(auto e:g[i]){ rev[e].emplace_back(i); } int idx=0; std::vector<int>v(n,-1); std::vector<bool>visited(n,0); auto dfs=[&](auto dfs,int now)->void{ visited[now]=1; for(auto e:g[now]){ if(!visited[e])dfs(dfs,e); } v[idx++]=now; }; for(int i=0;i<n;i++){ if(!visited[i])dfs(dfs,i); } idx=-1; std::vector<int>res(n,-1); auto rdfs=[&](auto rdfs,int now)->void{ for(auto e:rev[now]){ if(res[e]==-1)res[e]=idx,rdfs(rdfs,e); } }; for(int i=n-1;i>=0;--i){ if(res[v[i]]==-1){ res[v[i]]=++idx; rdfs(rdfs,v[i]); } } idx++; std::vector<std::vector<int>>res2(idx); for(int i=0;i<n;i++)for(auto e:g[i]){ if(res[i]==res[e])continue; res2[res[i]].push_back(res[e]); } for(int i=0;i<idx;i++){ std::sort(res2[i].begin(),res2[i].end()); res2[i].erase(std::unique(res2[i].begin(),res2[i].end()),res2[i].end()); } return {res,res2}; }