POJ 3177
题目大意
暂无
题目解法
暂无
RTFC
#include <cstdio>
inline int min(int a, int b) { return a < b ? a : b; }
int head[5010], to[20010], next[20010], ecnt, map[5010][5010];
int dfn[5010], low[5010], idx, cnt[5010];
void addEdge(int f, int t)
{
ecnt++;
next[ecnt] = head[f];
head[f] = ecnt;
to[ecnt] = t;
}
void tarjan(int u, int p)
{
dfn[u] = low[u] = ++idx;
for (int e = head[u]; e; e = next[e])
if (!dfn[to[e]])
tarjan(to[e], u), low[u] = min(low[u], low[to[e]]);
else if (to[e] != p)
low[u] = min(low[u], dfn[to[e]]);
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1, x, y; i <= m; i++)
{
scanf("%d%d", &x, &y);
if (!map[x][y])
{
addEdge(x, y);
addEdge(y, x);
map[x][y] = map[y][x] = true;
}
}
tarjan(1, 0);
for (int i = 1; i <= n; i++)
for (int e = head[i]; e; e = next[e])
if (low[to[e]] != low[i])
cnt[low[i]]++;
int ans = 0;
for (int i = 1; i <= n; i++)
ans += cnt[i] == 1;
printf("%d", (ans + 1) >> 1);
return 0;
}