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 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88
| #include<cstdio> #include<algorithm> #include<ctype.h> #include<string.h> #include<math.h>
using namespace std; #define ll long long
inline char read() { static const int IN_LEN = 1000000; static char buf[IN_LEN], *s, *t; return (s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin), (s == t ? -1 : *s++) : *s++); } template<class T> inline void read(T &x) { static bool iosig; static char c; for (iosig = false, c = read(); !isdigit(c); c = read()) { if (c == '-') iosig = true; if (c == -1) return; } for (x = 0; isdigit(c); c = read()) x = ((x + (x << 2)) << 1) + (c ^ '0'); if (iosig) x = -x; } const int OUT_LEN = 10000000; char obuf[OUT_LEN], *ooh = obuf; inline void print(char c) { if (ooh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh = obuf; *ooh++ = c; } template<class T> inline void print(T x) { static int buf[30], cnt; if (x == 0) print('0'); else { if (x < 0) print('-'), x = -x; for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48; while (cnt) print((char)buf[cnt--]); } } inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }
const int N = 50005, M = 60005; int n, m, num=1, cnt, top, p, dfn[N], low[N], stk[N], h[N], f[N][2], e[M<<1], pre[M<<1]; vector<int> E[N<<1]; inline void add(int x, int y){ e[++num]=y, pre[num]=h[x], h[x]=num;} void tarjan(int u, int fa=0){ dfn[u]=low[u]=++cnt; stk[++top]=u; for(int i=h[u]; i; i=pre[i]) if(i!=fa) if(!dfn[e[i]]){ tarjan(e[i], i^1), low[u]=min(low[u], low[e[i]]); if(dfn[e[i]]==low[e[i]]) E[u].push_back(e[i]); } else if(dfn[e[i]]<dfn[u]){ low[u]=min(low[u], dfn[e[i]]); E[e[i]].push_back(++p); for(int j=top; stk[j]!=e[i]; --j) E[p].push_back(stk[j]); } --top; } void dfs(int u){ for(int v:E[u]) dfs(v); if(u<=n){ f[u][1]=1; for(int v:E[u]) f[u][0]+=max(f[v][0], f[v][1]), f[u][1]+=f[v][0]; } else{ static int g[2], gg[2]; g[0]=-1e9, g[1]=0; for(int v:E[u]) gg[0]=max(g[0], g[1])+f[v][0], gg[1]=g[0]+f[v][1], swap(g, gg); f[u][0]=g[0]; g[0]=0, g[1]=-1e9; for(int v:E[u]) gg[0]=max(g[0], g[1])+f[v][0], gg[1]=g[0]+f[v][1], swap(g, gg); f[u][1]=max(g[0], g[1]); } } int main() { read(n), read(m), p=n; for(int i=1; i<=m; ++i){ static int x, y; read(x), read(y); add(x, y), add(y, x); } tarjan(1), dfs(1); return printf("%d", max(f[1][0], f[1][1])), 0; }
|