请求支援!!!80分,第三个测试点没过。大佬们帮帮忙!
查看原帖
请求支援!!!80分,第三个测试点没过。大佬们帮帮忙!
1740609
lqy202400091楼主2025/7/28 20:22

据说,我第三个测试点WA的原因是第一行太长了。

#include<cstdio>
#include<deque>
#include<algorithm>
using std::deque;
deque<deque<int>> gx;
deque<int> fs,DFS_ans,BFS_ans,du;
deque<bool> cl;
int n, m,u,i;
int main()
{
	scanf("%d %d", &n, &m);
	gx.resize(n + 1),cl.resize(n + 1),du.resize(n+1);
	for (int v, i = 0; i < m; ++i)
	{
		scanf("%d %d", &u, &v);
		gx[u].push_back(v);
	}
	for (auto& c : gx)
	{
		std::sort(c.begin(), c.end());
	}
	//DFS
	for (int i = 1; i <= n; ++i)
	{
		du[i] = gx[i].size()-1;
	}
	i = 1;
	while (i <= n)
	{
		while (!fs.empty())
		{
			u = fs[0];
			
			if (!cl[u])
				DFS_ans.push_back(u);
			cl[u]=true;
			fs.erase(fs.begin());
			for (; du[u]>=0; --du[u])
			{
				if (!cl[gx[u][du[u]]])
				{
					fs.push_front(gx[u][du[u]]);					
				}
			}			
		}
		for(;i<=n;++i)
			if (!cl[i])
			{
				fs.push_back(i);
				++i;
				break;
			}
	}
	//BFS
	i = 1;
	while (i<=n)
	{
		while (!fs.empty())
		{
			u = fs[0];
			if (cl[u])
				BFS_ans.push_back(u);
			cl[u] = 0;
			fs.erase(fs.begin());
			for (auto c : gx[u])
				if (cl[c])
					fs.push_back(c);
		}
		for(;i<=n;++i)
			if (cl[i])
			{
				fs.push_back(i);
				++i;
				break;
			}
	}
	//输出
	for (auto c : DFS_ans)
	{
		n = c;
		printf("%d ", n);
	}
	printf("\n");
	for (auto c : BFS_ans)
	{
		m = c;
		printf("%d ", m);
	}
	printf("\n");
}

哪位大佬可以指点一下?

2025/7/28 20:22
加载中...