蒟蒻求教
查看原帖
蒟蒻求教
205782
R浩轩泽Anmicius楼主2020/6/27 13:12

中考一段时间没有勤加练习,如今已经沦落到搜索跑图还会3WA 2TLE的地步了......

代码奉上:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define N 100005
#define E 1000005
#define inf 1e10
queue<int>q;//bfs存入点 
int num,head[E];
int n,m;
bool vis[N];
struct Edge{
	int next;
	int sta;
	int to;
	//int val;
}edge[E];
bool cmp(Edge x,Edge y)//由于先看编号较小的,因此需要按照终点排序 
{
	if(x.to==y.to)return x.sta>y.sta;//若终点相同,则按起点排序 
	return x.to>y.to;//前向星是逆序查找,因而调整使终点较小的边较后
}
void AddEdge(int x,int y)
{
	edge[++num].next=head[x];
	edge[num].sta=x;
	edge[num].to=y;
	head[x]=num;
}//前向星存边 
void dfs(int p)
{
	if(vis[p])return;
	cout<<p<<' ';//当前搜索到了p点 
	vis[p]=true;
	for(register int i=head[p];i!=-1;i=edge[i].next)
	dfs(edge[i].to);//深入下个节点 
} 
void bfs(int p)
{
	q.push(p);
	while(!q.empty())
	{
		int z=q.front();
		q.pop();		
		cout<<z<<' ';
		vis[z]=true;//已访问 
		for(register int i=head[z];i!=-1;i=edge[i].next)//枚举边 
		if(!vis[edge[i].to])q.push(edge[i].to);//bfs入队 
	}
}
int main()
{
	ios::sync_with_stdio(false);
	memset(head,-1,sizeof(head));//dfs枚举边 
	cin>>n>>m;
	for(register int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		AddEdge(x,y);
	}
	sort(edge+1,edge+m+1,cmp);//排序 
	memset(vis,false,sizeof(vis));	//是否访问过 
	dfs(1);
	cout<<'\n';
	memset(vis,false,sizeof(vis));	
	bfs(1);
	return 0;
}

恳请各位大佬指明错误之处~

2020/6/27 13:12
加载中...