|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 5010, M = 10010;
|
|
|
int n, m;
|
|
|
int d[N]; // 边双连通分量块的度
|
|
|
|
|
|
// 链式前向星
|
|
|
int e[M], h[N], idx, w[M], ne[M];
|
|
|
void add(int a, int b, int c = 0) {
|
|
|
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
|
|
|
}
|
|
|
|
|
|
// 边双连通分量
|
|
|
int dfn[N], low[N], ts, stk[N], top, root;
|
|
|
vector<int> bcc[N]; // 边双中有哪些原始点,集合-> 点
|
|
|
int id[N], bcnt; // 原始点x属于哪个边双连通分量，bcnt指边双连通分量个数,点->集合
|
|
|
int is_bridge[M]; // 哪些边是割边
|
|
|
|
|
|
void tarjan(int u, int from) {
|
|
|
dfn[u] = low[u] = ++ts;
|
|
|
stk[++top] = u;
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
int v = e[i];
|
|
|
if (!dfn[v]) {
|
|
|
tarjan(v, i);
|
|
|
low[u] = min(low[u], low[v]);
|
|
|
if (dfn[u] < low[v]) is_bridge[i] = is_bridge[i ^ 1] = 1; // 记录割边
|
|
|
} else if (i != (from ^ 1))
|
|
|
low[u] = min(low[u], dfn[v]);
|
|
|
}
|
|
|
|
|
|
if (dfn[u] == low[u]) {
|
|
|
++bcnt; // 边双号
|
|
|
int x;
|
|
|
do {
|
|
|
x = stk[top--];
|
|
|
id[x] = bcnt; // 记录点与边双关系
|
|
|
bcc[bcnt].push_back(x); // 记录边双中有哪些点
|
|
|
} while (x != u);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
memset(h, -1, sizeof h);
|
|
|
scanf("%d %d", &n, &m);
|
|
|
while (m--) {
|
|
|
int a, b;
|
|
|
scanf("%d %d", &a, &b);
|
|
|
if (a != b) add(a, b), add(b, a);
|
|
|
}
|
|
|
// Tarjan算法缩点，生成边双连通分量, 缩点后，新图中的边将只是割边。
|
|
|
// 注意：这里并没有真的创建新图，而是心中有图而手中无图。
|
|
|
// 获取边双连通分量的过程中，记录了哪些边是割边，下面将利用割边解决问题
|
|
|
for (root = 1; root <= n; root++)
|
|
|
if (!dfn[root]) tarjan(root, -1);
|
|
|
|
|
|
// 下面统计新图中每个点的度,这是一个经典用法，需要理解和记忆
|
|
|
// 计算新图中度为1的点(边双连通分量)的个数，也就是叶子节点的个数
|
|
|
for (int u = 1; u <= n; u++) // ①枚举每个原始点
|
|
|
for (int i = h[u]; ~i; i = ne[i]) { // ②枚举此点的每条出边
|
|
|
// (1) 由于每个节点都可以从1~n枚举到，所以u->v,v->u也都可以被枚举到
|
|
|
// (2) 由于割边是成对出现，而成对的割边都可以通过出边的方式被枚举到，也就是成对的割边
|
|
|
// 为两个节点都提供了一个度，这个度可以理解为在无向图中某个点的连接边数，
|
|
|
// 这个边数可不是a->b,b->a这样的形式，只是a-b
|
|
|
int v = e[i];
|
|
|
// 如果某条边是割边，说明它在新图中是存在的边
|
|
|
if (is_bridge[i]) d[id[v]]++; // 如果此边是割边,则新点的度++
|
|
|
}
|
|
|
|
|
|
// 度为1的是叶子
|
|
|
int cnt = 0;
|
|
|
for (int i = 1; i <= bcnt; i++) // 注意：模板中的bcnt是从1开始的
|
|
|
if (d[i] == 1) cnt++; // 多少个度为1的节点(边双连通分量)
|
|
|
|
|
|
// 贪心,叶子结点的除以2上取整即是答案
|
|
|
printf("%d\n", (cnt + 1) / 2);
|
|
|
return 0;
|
|
|
}
|
