This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0377 #include<bits/stdc++.h> using namespace std; #define call_from_test #include "../../tools/fixpoint.cpp" #include "../../graph/twoedgeconnectedcomponents.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n,m; cin>>n>>m; TwoEdgeConnectedComponents tecc(n); for(int i=0;i<m;i++){ int a,b; cin>>a>>b; tecc.add_edge(a,b); } int k=tecc.build(); auto G=tecc.forest(); vector<int> cs(k); for(int i=0;i<k;i++) cs[i]=tecc[i].size(); vector<vector<int>> dp(2,vector<int>(k,0)); vector<int> used(k,0); auto dfs= MFP([&](auto dfs,int v,int p)->void{ if(used[v]) return; used[v]=1; dp[0][v]=0; dp[1][v]=cs[v]; for(int u:G[v]){ if(u==p) continue; dfs(u,v); dp[0][v]+=max(dp[0][u],dp[1][u]); dp[1][v]+=dp[0][u]; } return; }); int ans=0; for(int i=0;i<k;i++){ if(used[i]) continue; dfs(i,-1); ans+=max(dp[0][i],dp[1][i]); } cout<<ans<<endl; return 0; }
#line 1 "test/aoj/0377.test.cpp" // verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0377 #include<bits/stdc++.h> using namespace std; #define call_from_test #line 1 "tools/fixpoint.cpp" #line 3 "tools/fixpoint.cpp" using namespace std; #endif //BEGIN CUT HERE template<typename F> struct FixPoint : F{ FixPoint(F&& f):F(forward<F>(f)){} template<typename... Args> decltype(auto) operator()(Args&&... args) const{ return F::operator()(*this,forward<Args>(args)...); } }; template<typename F> inline decltype(auto) MFP(F&& f){ return FixPoint<F>{forward<F>(f)}; } //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #line 1 "graph/twoedgeconnectedcomponents.cpp" #line 3 "graph/twoedgeconnectedcomponents.cpp" using namespace std; #endif //BEGIN CUT HERE // work with multigraph struct TwoEdgeConnectedComponents{ vector<int> ord,low,par,blg,sz; vector<vector<int>> G,C; TwoEdgeConnectedComponents(int n): ord(n,-1),low(n),par(n,-1),blg(n,-1),sz(n,1),G(n){} void add_edge(int u,int v){ if(u==v) return; G[u].emplace_back(v); G[v].emplace_back(u); } bool is_bridge(int u,int v){ if(ord[u]>ord[v]) swap(u,v); return ord[u]<low[v]; } void dfs(int v,int &pos){ ord[v]=low[v]=pos++; int dup=0; for(int u:G[v]){ if(u==par[v] and !dup){ dup=1; continue; } if(~ord[u]){ low[v]=min(low[v],ord[u]); continue; } par[u]=v; dfs(u,pos); sz[v]+=sz[u]; low[v]=min(low[v],low[u]); } } void fill_component(int v){ C[blg[v]].emplace_back(v); for(int u:G[v]){ if(~blg[u] or is_bridge(u,v)) continue; blg[u]=blg[v]; fill_component(u); } } void add_component(int v,int &k){ if(~blg[v]) return; blg[v]=k++; C.emplace_back(); fill_component(v); } int build(){ int n=G.size(),pos=0; for(int i=0;i<n;i++) if(ord[i]<0) dfs(i,pos); int k=0; for(int i=0;i<n;i++) add_component(i,k); return k; } const vector<int>& operator[](int i)const{return C[i];} vector<vector<int>> forest(){ int n=G.size(),k=C.size(); vector<vector<int>> T(k); for(int v=0;v<n;v++) for(int u:G[v]) if(blg[v]!=blg[u]) T[blg[v]].emplace_back(blg[u]); return T; } }; //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #line 9 "test/aoj/0377.test.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n,m; cin>>n>>m; TwoEdgeConnectedComponents tecc(n); for(int i=0;i<m;i++){ int a,b; cin>>a>>b; tecc.add_edge(a,b); } int k=tecc.build(); auto G=tecc.forest(); vector<int> cs(k); for(int i=0;i<k;i++) cs[i]=tecc[i].size(); vector<vector<int>> dp(2,vector<int>(k,0)); vector<int> used(k,0); auto dfs= MFP([&](auto dfs,int v,int p)->void{ if(used[v]) return; used[v]=1; dp[0][v]=0; dp[1][v]=cs[v]; for(int u:G[v]){ if(u==p) continue; dfs(u,v); dp[0][v]+=max(dp[0][u],dp[1][u]); dp[1][v]+=dp[0][u]; } return; }); int ans=0; for(int i=0;i<k;i++){ if(used[i]) continue; dfs(i,-1); ans+=max(dp[0][i],dp[1][i]); } cout<<ans<<endl; return 0; }