test/aoj/0377.test.cpp

• View this file on GitHub
• Last update: 2020-10-27 16:01:15+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0377

Depends on

• graph/twoedgeconnectedcomponents.cpp
• tools/fixpoint.cpp

Code

// 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;
}

Back to top page