【题目链接】
洛谷 P5318 【深基18.例3】查找文献
【题目考点】
1. 图论：深度优先遍历
2. 图论：广度优先遍历
【解题思路】
首先将题目描述抽象为拓扑图，这是一个有向图，每篇文章是顶点，边<x,y>表示文章x有参考文献y。
“目前小K已经打开了编号为1的一篇文章”，意为只从1号顶点出发开始进行搜索。要做的是从1号顶点一趟搜索，并不需要把给出的所有文章都遍历到。
邻接矩阵的空间复杂度是
O
(
V
2
)
O(V^2)
O(V2)，邻接表的空间复杂度是
O
(
V
+
E
)
O(V+E)
O(V+E)，该题中顶点数V达到
1
0
5
10^5
105，边数E达到
1
0
6
10^6
106。如果使用邻接矩阵，声明变量的数量会达到
1
0
10
10^{10}
1010，是不可接受的（最大可以到
1
0
7
10^7
107）。
因此本题只能使用邻接表求解。文章来源：https://www.toymoban.com/news/detail-673822.html
“如果有很多篇文章可以参阅，请先看编号较小的那篇”：
如果使用邻接表保存，那么vector<int>类型的edge[u]中保存的u的邻接点必须是从小到大排列的。
实现方法有以下几种，复杂度都是
O
(
n
)
O(n)
O(n)：文章来源地址https://www.toymoban.com/news/detail-673822.html
//vec插入数值v，保持vec中的元素是升序的
//方法1：插入排序
void seqIns1(vector<int> &vec, int v)
{
vec.push_back(v);
for(int i = vec.size()-1; i > 0; --i)
if(vec[i] < vec[i-1])
swap(vec[i], vec[i-1]);
}
//方法2：顺序查找待插入的位置并插入
void seqIns2(vector<int> &vec, int v)
{
vector<int>::iterator it;
for(it = vec.begin(); it != vec.end(); ++it)
if(*it >= v)
break;
vec.insert(it, v);//迭代器it指向第一个大于等于v的最小值，在it指向的元素前面插入v
}
//方法3：二分查找待插入位置并插入
void seqIns3(vector<int> &vec, int v)
{
vec.insert(lower_bound(vec.begin(), vec.end(), v), v);
}
【题解代码】
解法1：使用邻接表
- 写法1：插入排序构造有序vector
#include<bits/stdc++.h>
using namespace std;
#define N 100005
vector<int> edge[N];//edge[i]：保存i的所有邻接点
bool vis[N];//vis[i]：顶点i是否已访问
int n, m;//n：顶点数 m：边数
void dfs(int u)
{
for(int v : edge[u])
{
if(vis[v] == false)
{
vis[v] = true;
cout << v << ' ';
dfs(v);
}
}
}
void bfs(int sv)
{
queue<int> que;
vis[sv] = true;
cout << sv << ' ';
que.push(sv);
while(que.empty() == false)
{
int u = que.front();
que.pop();
for(int v : edge[u])
{
if(vis[v] == false)
{
vis[v] = true;
cout << v << ' ';
que.push(v);
}
}
}
}
void seqIns(int f, int t)//顶点f添加邻接点t，保持edge[f]升序
{
edge[f].push_back(t);
for(int i = edge[f].size()-1; i > 0; --i)
if(edge[f][i] < edge[f][i-1])
swap(edge[f][i], edge[f][i-1]);
}
int main(){
int f, t;
cin >> n >> m;
for(int i = 1; i <= m; i++){
cin >> f >> t;
seqIns(f, t);
}
vis[1] = true;
cout << 1 << ' ';
dfs(1);
cout<<endl;
memset(vis,false,sizeof(vis));
bfs(1);
return 0;
}
- 写法2：二分查找加插入构造有序vector
#include<bits/stdc++.h>
using namespace std;
#define N 100005
vector<int> edge[N];//edge[i]：保存i的所有邻接点
bool vis[N];//vis[i]：顶点i是否已访问
int n, m;//n：顶点数 m：边数
void dfs(int u)
{
for(int v : edge[u])
{
if(vis[v] == false)
{
vis[v] = true;
cout << v << ' ';
dfs(v);
}
}
}
void bfs(int sv)
{
queue<int> que;
vis[sv] = true;
cout << sv << ' ';
que.push(sv);
while(que.empty() == false)
{
int u = que.front();
que.pop();
for(int v : edge[u])
{
if(vis[v] == false)
{
vis[v] = true;
cout << v << ' ';
que.push(v);
}
}
}
}
int main(){
int f, t;
cin >> n >> m;
for(int i = 1; i <= m; i++){
cin >> f >> t;
edge[f].insert(lower_bound(edge[f].begin(), edge[f].end(), t), t);
}
vis[1] = true;
cout << 1 << ' ';
dfs(1);
cout<<endl;
memset(vis,false,sizeof(vis));
bfs(1);
return 0;
}
到了这里，关于洛谷 P5318 【深基18.例3】查找文献的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
