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 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131
| #pragma GCC optimize(2) #pragma GCC optimize(3, "Ofast", "inline") #include<bits/stdc++.h> using namespace std;
typedef long long ll; typedef __int128 int128;
namespace FastIO { char buf[1 << 20], *p1, *p2; #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++) template<typename T> inline T read(T& x) { x = 0; int f = 1; char ch; while (!isdigit(ch = getchar())) if (ch == '-') f = -1; while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar(); x *= f; return x; } template<typename T, typename... Args> inline void read(T& x, Args &...x_) { read(x); read(x_...); return; } inline ll read() { ll x; read(x); return x; } inline void read(char *s) { scanf("%s", s + 1); } }; using namespace FastIO;
const int N = 1010; const int M = 2010;
class Graph { private : struct Edge { int to, nt, wt; Edge() {} Edge(int to, int nt, int wt) : to(to), nt(nt), wt(wt) {} }e[M]; int hd[N], cnte; public : void AddEdge(int u, int v, int w = 0) { e[++cnte] = Edge(v, hd[u], w); hd[u] = cnte; } int head(int u) { return hd[u]; } int nt(int u) { return e[u].nt; } int to(int u) { return e[u].to; } int wt(int u) { return e[u].wt; } };
int n, m; Graph e; int uid[M], vid[M];
inline void Input() { read(n, m); int u, v; for(int i = 1; i <= m; i++) { read(uid[i], vid[i]); e.AddEdge(uid[i], vid[i]); e.AddEdge(vid[i], uid[i]); } }
int low[N], dfn[N], cntd; int vis[N]; stack<int >st; int cl[N], cntc;
int inD[N];
inline void Tarjan(int u, int fa) { vis[u] = 1; low[u] = dfn[u] = ++cntd; st.push(u); for(int i = e.head(u); i ; i = e.nt(i)) { int v = e.to(i); if(v == fa) continue; if(!dfn[v]) { Tarjan(v, u); low[u] = min(low[u], low[v]); } else if(vis[v]) { low[u] = min(low[u], dfn[v]); } } if(dfn[u] == low[u]){ int v = 0; ++cntc; while(u != v) { v = st.top(); st.pop(); cl[v] = cntc; vis[v] = 0; } } }
inline void Work() { Tarjan(1, 1); for(int i = 1; i <= m; i++) { if(cl[uid[i]] != cl[vid[i]]) { inD[cl[uid[i]]]++; inD[cl[vid[i]]]++; } } int ans = 0; for(int i = 1; i <= cntc; i++) { if(inD[i] == 1) ans++; } printf("%d", ans + 1 >> 1); }
int main() { int T = 1; while(T--) { Input(); Work(); } return 0; }
|