/
0377.test.cpp
54 lines (47 loc) · 1.13 KB
/
0377.test.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// 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;
}