可是我一遍就过了啊
by 华年 @ 2022-07-21 17:44:13
先贴一个我的代码
基本思路也是先缩点, 再建新图, 再统计叶子数(我用的 dfs).
等下我看看你的代码
```cpp
#include <stack>
#include <stdio.h>
#include <memory.h>
#include <algorithm>
#define eto e[i].to
#define etoo e2[i].to
#define en e[i].n
#define enn e2[i].n
const int maxn = 1e4 + 5, maxm = 1e5 + 6;
typedef int imaxn[maxn];
// scc, strong connected component, 强连通分量
// dfn 是时间戳
// low 是能够追溯到的最早的栈中节点的时间戳.
imaxn head, head2, dfn, low, scc, degree, dp, flag;
int cnt, cnt2, idx, n, m, dfsClock;
std::stack<int> s;
struct edge { int to, n; } e[maxm * 2], e2[maxm * 2]; // 有向图
void add(int u, int v) { e[++cnt].to = v; e[cnt].n = head[u]; head[u] = cnt; }
void add2(int u, int v) { e2[++cnt2].to = v; e2[cnt2].n = head2[u]; head2[u] = cnt2; }
void tarjan(int, int);
void dfs(int);
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
scanf("%d %d", &n, &m);
for (int i = 1, u, v;i <= m;i++)
{
scanf("%d %d", &u, &v);
add(u, v);
add(v, u);
}
for (int i = 1;i <= n;i++)
if (!dfn[i])
tarjan(i, 0);
// 建立新图
for (int u = 1;u <= n;u++)
for (int i = head[u];i;i = en)
if (scc[u] != scc[eto])
{
add2(scc[u], scc[eto]);
add2(scc[eto], scc[u]);
// printf("%d -> %d\n", scc[u], scc[eto]);
}
dfs(1);
int ans = 0;
for (int i = 1;i <= idx;i++)
if (degree[i] == 1)
ans++;
printf("%d", (ans + 1) / 2);
return 0;
}
void tarjan(int u, int fa)
{
dfn[u] = low[u] = ++dfsClock; // 更新时间戳
s.push(u);
for (int i = head[u];i;i = en)
{
if (eto == fa)
continue;
if (!dfn[eto])
{
tarjan(eto, u);
low[u] = std::min(low[u], low[eto]); // 自己和自己的儿子在同一个 scc 中
}
else if (!scc[eto]) // 如果他的儿子已经被更新过了, 并且这个儿子不在已知的强连通分量中, 那么这个儿子和自己在同一个 scc 中, 并且这个儿子有可能就是所在 scc 中 dfn 最小的一个
low[u] = std::min(low[u], dfn[eto]);
}
if (dfn[u] == low[u]) // 自己是自己所在的 scc 中 dfn 最小的一个
{
idx++;
int x;
// printf("[%d] : ", idx);
while (true)
{
x = s.top(); s.pop();
// printf("%d ", x);
scc[x] = idx;
if (x == u)
break;
}
// puts("");
}
}
void dfs(int u)
{
flag[u] = true;
for (int i = head2[u];i;i = enn)
if (!flag[etoo])
{
degree[u]++;
degree[etoo]++;
dfs(etoo);
}
return;
}
```
by 华年 @ 2022-07-21 17:47:25
与代码本身有关的细节放在[这里](https://www.luogu.com.cn/paste/xe3oglbz)了
接下来说一下我看出来的你原来的做法所存在的问题
我其实不知道你想怎么用你标记的桥的, 写了一大段最后还是删了. 不过不用讨论了, 你明白就行, 可以尝试一下把你的版本改对.
这里也许有问题.
```cpp
for(int i = first[x]; i&&((!mark[i])&&(!mark[i^1])); i = edge[i].next)
{
int y = edge[i].to;
if(!vis[y]) dfs(y);
}
```
也许应该是这样才正确
```cpp
for(int i = first[x];i;i = edge[i].next)
if (!mark[i] && !mark[i^1])
{
int y = edge[i].to;
if(!vis[y]) dfs(y);
}
```
不解释了, 你应该能明白. 改了这个地方之后 #2 就 A 了好像.
还有这个地方
```cpp
for(int i = 2; i <= cnt; i++) //加入桥
{
if(!mark[i]) continue;
int x = edge[i].from;
int y = edge[i].to;
leaf[co[x]]++;
leaf[co[y]]++;
}
```
由于是无向图, 所以我第一眼就觉得这里有问题. 不过因为你跳过了标记的桥, 这些桥不在 scc 中, 所以无向图变成了有向图, 就没问题了.
后来 #9 #10 WA 了, 我下载数据一看, 发现有重边. 果然删掉重边之后就对了, 所以还是有问题.
解决方法我想到了两个, 一是 `dfs()` + `vis[]`, 二是拓扑排序. 我选择了第一种.
所以说你原来能得那么高的分, 说明数据有点水.
by 华年 @ 2022-07-21 21:08:56
@[华年](/user/240858) 感谢大佬细节说明，真是太巨了！！！
by Future_zxs @ 2022-07-21 22:41:04