为什么这样是对的
#include <bits/stdc++.h>
using namespace std;
vector <int> to[20010];
int dfn[20010], low[20010], son[20010];
bool vis[20010], ans[20010], rt[20010];
int it, cnt;
void trj(int i)
{
// cout << "in tarjan: " << i << endl;
dfn[i] = low[i] = ++it;
vis[i] = 1;
for (int j = 0; j < to[i].size(); j++)
if (! vis[to[i][j]])
{
trj(to[i][j]);
son[i]++;
low[i] = min(low[i], low[to[i][j]]);
if (! ans[i] && dfn[i] <= low[to[i][j]] && ! rt[i])
ans[i] = 1,
cnt++;
}
else
low[i] = min(low[i], dfn[to[i][j]]);
if (! ans[i] && rt[i] && son[i] > 1)
ans[i] = 1,
cnt++;
}
int main()
{
int n, m;
cin >> n >> m;
int u, v;
while (m--)
cin >> u >> v,
to[u].push_back(v),
to[v].push_back(u);
for (int i = 1; i <= n; i++)
if (! vis[i])
rt[i] = 1,
trj(i);
cout << cnt << endl;
for (int i = 1; i <= n; i++)
if (ans[i])
cout << i << " ";
cout << endl;
return 0;
}
而这样全WA,我可能唐了反正没看出什么区别
#include <bits/stdc++.h>
using namespace std;
vector <int> to[20010];
int dfn[20010], low[20010], son[20010];
bool vis[20010], ans[20010], rt[20010];
int it, cnt;
void trj(int i)
{
// cout << "in tarjan: " << i << endl;
dfn[i] = low[i] = ++it;
vis[i] = 1;
for (int j = 0; j < to[i].size(); j++)
{
if (! vis[to[i][j]])
trj(to[i][j]),
son[i]++,
low[i] = min(low[i], low[to[i][j]]);
else
low[i] = min(low[i], dfn[to[i][j]]);
if (! ans[i] && ((dfn[i] <= low[to[i][j]] && ! rt[i]) || (rt[i] && son[i] > 1)))
ans[i] = 1,
cnt++;
}
}
int main()
{
int n, m;
cin >> n >> m;
int u, v;
while (m--)
cin >> u >> v,
to[u].push_back(v),
to[v].push_back(u);
for (int i = 1; i <= n; i++)
if (! vis[i])
rt[i] = 1,
trj(i);
cout << cnt << endl;
for (int i = 1; i <= n; i++)
if (ans[i])
cout << i << " ";
cout << endl;
return 0;
}