洛谷P5318

分析

关键词

• n篇文章
• m条参考文献引用关系
• x文章有y参考文献
• BFS&&DFS结果

步骤

1. 定义 不仅要定义关键词，还要再定义一个容器 这里用\(set\)

set<int>e[100009];

注意要初始化

2. 输入 输入n m x y这几个关键字

3. 计算过程 分两步

• 深搜
• 广搜

4. 输出 先调用函数，在输出结果

代码

伪代码

定义数组，同时定义 n m x y
void init(){
  输入
  初始化
}
void dfs(){
  标记走过 
  输出
  标记
}
void bfs(){
  定义队列
  初始化
  while(){
    判断
    输出
    标记
  }
}
int main(){
  init();
  dfs（）；
  putchar
  memset
  bfs();
  putchar
  return 0;
}

\(Code\)

#include<bits/stdc++.h>
using namespace std;
int n,m;
set<int>e[100009];
bool vis[100009];
void init(){
	for(scanf("%d%d",&n,&m);m;--m){
		int u=0,v=0;
		scanf("%d%d",&u,&v);
		e[u].insert(v);
	}
}
void dfs(int x=1){
	if(vis[x])return;vis[x]=1;
	printf("%d ",x);
	for(int v:e[x])dfs(v);
}
void bfs(){
	queue<int>q;
	q.push(1);
	while(!q.empty()){
		int x=q.front();q.pop();
		if(vis[x])continue;vis[x]=1;
		printf("%d ",x);
		for(int v:e[x])q.push(v);
	}
}
int main(){
	init();
	dfs();
	putchar('\n');
	memset(vis,0,sizeof(vis));
	bfs();
	putchar('\n');
	return 0;
}