Bodhi @ 2023-04-02 23:06:44
RT
第一份代码的tarjan函数（使用边的编号判重）：
void tarjan(int x, int frome)//
{
low[x] = dfn[x] = ++tme;
int to;
for (int i = head[x]; ~i; i = e[i].next)
{
to = e[i].to;
if (!dfn[to])
{
tarjan(to, i);//
low[x] = min(low[x], low[to]);
if (dfn[x] < low[to])
e[i].flag = e[i ^ 1].flag = true;
}
else if (i != (frome ^ 1))//
low[x] = min(low[x], dfn[to]);
}
}第二份的tarjan（使用to!=fa，未使用其他判重方式）
void tarjan(int x, int fa)//
{
low[x] = dfn[x] = ++tme;
int to;
for (int i = head[x]; ~i; i = e[i].next)
{
to = e[i].to;
if (!dfn[to])
{
tarjan(to, x);//
low[x] = min(low[x], low[to]);
if (dfn[x] < low[to])
e[i].flag = e[i ^ 1].flag = true;
}
else if (to != fa)//
low[x] = min(low[x], dfn[to]);
}
}（有标记注释的是不一样的地方）
输入数据
4 4
1 2
2 3
2 4
2 4按照第二种写法，本来应该是错的
然而测试之后，发现两份代码都输出了正确答案
请问这是什么原因呢？
by Bodhi @ 2023-04-02 23:08:21
方便各位大佬调试的QwQ
#include <bits/stdc++.h>
using namespace std;
const int M = 2e6 + 10, N = 5e5 + 10;
struct Edge
{
int to, next;
bool flag;
} e[M * 2];
int head[M * 2], tot = 0;
int low[N], dfn[N], tme, anscnt;
vector<int> ans[N];
bool b[N];
void add(int x, int y)
{
e[tot] = {
.to = y,
.next = head[x]};
head[x] = tot;
++tot;
}
void tarjan(int x, int fa)//
{
low[x] = dfn[x] = ++tme;
int to;
for (int i = head[x]; ~i; i = e[i].next)
{
to = e[i].to;
if (!dfn[to])
{
tarjan(to, x);//
low[x] = min(low[x], low[to]);
if (dfn[x] < low[to])
e[i].flag = e[i ^ 1].flag = true;
}
else if (to != fa)//
low[x] = min(low[x], dfn[to]);
}
}
void dfs(int x)
{
b[x] = true;
ans[anscnt].push_back(x);
int to;
for (int i = head[x]; ~i; i = e[i].next)
{
to = e[i].to;
if (!b[to] && !e[i].flag)
dfs(to);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m, x, y, j;
memset(head, -1, sizeof(head));
cin >> n >> m;
for (j = 1; j <= m; ++j)
{
cin >> x >> y;
if (x != y)
add(x, y), add(y, x);
}
for (j = 1; j <= n; ++j)
if (!dfn[j])
tarjan(j, 0);
for (j = 1; j <= n; ++j)
if (!b[j])
{
++anscnt;
dfs(j);
}
cout << anscnt << '\n';
for (int i = 1; i <= anscnt; ++i)
{
cout << ans[i].size() << ' ';
for (auto j : ans[i])
cout << j << ' ';
cout << '\n';
}
return 0;
}
by lyc1001 @ 2023-04-04 21:22:02
@Bodhi 改成else if(vis[v])都行
by Bodhi @ 2023-04-04 21:28:30
@lyc1001 但是为啥啊，按原理来说应该是不对的
by lyc1001 @ 2023-09-21 22:36:29
@Bodhi 因为这题没有重边，如果有重边，那u和v显然是缩成一个点。用vis判断的话，u走到v后，v不会反过来用u来更新自身，于是在v层就自己缩成一个点了。而用编号判断，只是不反过来走本条边，但是可以通过重边里的另一条边去接触到u,于是在v层不缩点，回到u层缩在一起。