藍(lán)橋杯備賽 | 洛谷做題打卡day5

圖論起航，一起來看看深（廣）度優(yōu)先吧 ~

【深基18.例3】查找文獻(xiàn)

題目描述

小 K 喜歡翻看洛谷博客獲取知識(shí)。每篇文章可能會(huì)有若干個(gè)（也有可能沒有）參考文獻(xiàn)的鏈接指向別的博客文章。小 K 求知欲旺盛，如果他看了某篇文章，那么他一定會(huì)去看這篇文章的參考文獻(xiàn)（如果他之前已經(jīng)看過這篇參考文獻(xiàn)的話就不用再看它了）。

假設(shè)洛谷博客里面一共有 $n(n\le 10^5)$ 篇文章（編號(hào)為 1 到 $n$）以及 $m(m\le 10^6)$ 條參考文獻(xiàn)引用關(guān)系。目前小 K 已經(jīng)打開了編號(hào)為 1 的一篇文章，請(qǐng)幫助小 K 設(shè)計(jì)一種方法，使小 K 可以不重復(fù)、不遺漏的看完所有他能看到的文章。

這邊是已經(jīng)整理好的參考文獻(xiàn)關(guān)系圖，其中，文獻(xiàn) X → Y 表示文章 X 有參考文獻(xiàn) Y。不保證編號(hào)為 1 的文章沒有被其他文章引用。

請(qǐng)對(duì)這個(gè)圖分別進(jìn)行 DFS 和 BFS，并輸出遍歷結(jié)果。如果有很多篇文章可以參閱，請(qǐng)先看編號(hào)較小的那篇(因此你可能需要先排序)。

輸入格式

共 $m+1$ 行，第 1 行為 2 個(gè)數(shù)，$n$ 和 $m$，分別表示一共有 $n(n\le 10^5)$ 篇文章（編號(hào)為 1 到 $n$）以及$m(m\le 10^6)$ 條參考文獻(xiàn)引用關(guān)系。

接下來 $m$ 行，每行有兩個(gè)整數(shù) $X,Y$ 表示文章 X 有參考文獻(xiàn) Y。

輸出格式

共 2 行。
第一行為 DFS 遍歷結(jié)果，第二行為 BFS 遍歷結(jié)果。

樣例 #1

樣例輸入 #1

8 9
1 2
1 3
1 4
2 5
2 6
3 7
4 7
4 8
7 8

樣例輸出 #1

1 2 5 6 3 7 8 4 
1 2 3 4 5 6 7 8

學(xué)會(huì)利用新知，自己多試試并嘗試積攢一些固定解答方案，debug，以下是我的代碼 ~

#include<iostream>  //頭文件不要忘記啦
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
inline int read()//二進(jìn)制優(yōu)化的快讀 
{
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch>'9')
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9')
	{
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
int n, m;
bool b[100005];//定義b數(shù)組防止重復(fù)輸出 
vector<int > a[100005];//STL大法好 
void dfs(int x, int r)//x表示所在點(diǎn)，r表示剩余未遍歷的點(diǎn) 
{
	b[x] = true;//記錄某點(diǎn)已經(jīng)輸出過 
	if (!r)//如果每個(gè)點(diǎn)都遍歷過終止遞歸 
	{
		cout << x << ' ';
		return;
	}
	cout << x << ' ';//輸出 
	for (int i = 0; i < a[x].size(); i++)
		if (!b[a[x][i]]) dfs(a[x][i], r - 1);//查找從x可以到的點(diǎn)，并遍歷 
}
void bfs()
{
	queue<int> q;//還是STL 
	q.push(1); b[1] = true;//把1點(diǎn)放入隊(duì)列中，并標(biāo)記1點(diǎn)已經(jīng)遍歷過 
	while (!q.empty())
	{
		int s = q.front(); q.pop();//拿出隊(duì)列首的那個(gè)點(diǎn) 
		cout << s << ' ';//輸出 
		for (int i = 0; i < a[s].size(); i++) if (b[a[s][i]] == false) q.push(a[s][i]), b[a[s][i]] = true;//把點(diǎn)s所能到達(dá)的點(diǎn)遍歷，為防止TLE和重復(fù)輸出，記錄已遍歷過的點(diǎn) 
	}
}
int main()
{
	n = read();//讀入 
	m = read();
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		x = read();//讀入
		y = read();
		a[x].push_back(y);//建圖 表示x可以到y(tǒng) 
	}
	for (int i = 1; i <= n; i++)//把每條路所通向的點(diǎn)從小到大排列（題目中有要求） 
		sort(a[i].begin(), a[i].end());//快排  
	dfs(1, n);//進(jìn)行深搜 從1點(diǎn)開始，進(jìn)行n次 
	cout << endl;//換行 
	for (int i = 1; i <= n; i++) b[i] = false;//初始化 
	bfs();//進(jìn)行廣搜 
	return 0;
}

文章來源地址http://www.zghlxwxcb.cn/news/detail-796053.html

我的一些話

• 關(guān)于圖論：ww圖論確實(shí)難度要吊打之前的普通題，但人總是要學(xué)會(huì)跳出之前的泥淖，才能看見更遠(yuǎn)的星辰?；蛟S這條路不好走，但要加油呀！學(xué)會(huì)利用新知，自己多試試并嘗試積攢一些固定解答方案，大多數(shù)人的努力，其實(shí)還沒有到拼天賦的程度。在一切未知之前，我們能做的便是享受當(dāng)下并做自己喜歡且認(rèn)為有意義的事情。
• 總結(jié)來說思路很重要，多想想，多在草稿紙上畫畫，用測(cè)試數(shù)據(jù)多調(diào)試，debug后成功編譯并運(yùn)行出正確結(jié)果真的會(huì)感到很幸福！
• 關(guān)于之前藍(lán)橋杯備賽的路線和基本方法、要掌握的知識(shí)，之前的博文我都有寫，歡迎大家翻閱自取~
• 不管什么都要堅(jiān)持吧，三天打魚兩天曬網(wǎng)無法形成肌肉記憶和做題思維，該思考的時(shí)候一定不要懈怠，今天就說這么多啦，歡迎評(píng)論留言，一起成長(zhǎng)：）

到了這里，關(guān)于藍(lán)橋杯備賽 | 洛谷做題打卡day5的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！