已A但疑惑
查看原帖
已A但疑惑
1122193
FarmerDrone楼主2024/12/3 22:45

为什么这样是对的

#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;
} 
2024/12/3 22:45
加载中...