社区讨论

MLE20pts求调

P5318【深基18.例3】查找文献参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mhjrtcpq
此快照首次捕获于
2025/11/04 07:28
4 个月前
此快照最后确认于
2025/11/04 07:28
4 个月前
查看原帖
第一个点在不断优化,但不知怎的后面始终MLE
CPP
#include<bits/stdc++.h>
using namespace std;
struct node
{
	int number,temp=0,isvisit=0,isvisit1=0;
	vector<int> children;
}a[100001];
int n,m,bfsv[100001],tempa=0,tempb=0;
queue<int> q,q1;
void dfs(int s)
{
	if(a[s].temp==0)
	{
		return;
	}
	for(int i=0;i<a[s].temp;i++)
	{
		if(a[s].isvisit==0)
		{
			a[s].isvisit==1;
			q1.push(a[s].children[i]);
			dfs(a[s].children[i]);
		}
	}
}
void dfsc()
{
	cout<<1<<' ';
	tempa=n-1;
	while(tempa--)
	{
		cout<<q1.front()<<' ';
		q1.pop();
	}
}
void bfs(int s)
{
	if(a[s].temp==0)
	{
		return;
	}
	for(int i=0;i<a[s].temp;i++)
	{
		if(a[a[s].children[i]].isvisit1==0)
		{
			a[a[s].children[i]].isvisit1=1;
			q.push(a[s].children[i]);
		}
	}
	bfsv[tempb]=q.front();
	tempb++;
	q.pop();
	bfs(q.front());
}
void bfsc()
{
	for(int i=0;i<tempb;i++)
	{
		cout<<bfsv[i]<<' ';
	}
	while(!q.empty())
	{
		cout<<q.front()<<' ';
		q.pop();
	}
}
int main()
{
	q.push(1);
	bfsv[0]=1;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		a[i].number=i;
	}
	for(int i=0;i<m;i++)
	{
		int p,q;
		cin>>p>>q;
		a[p].children.push_back(q);
		a[p].temp++;
	}
	for(int i=0;i<n;i++)
	{
		sort(a[i].children.begin(),a[i].children.end());
	}
	dfs(1);
	dfsc();
	cout<<endl;
	bfs(1);
	bfsc();
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...