题目
解题思路
重点有两点：
- 使用vector建立无权有向图，并使用迭代器对图排序
- 深搜，访问节点，使用vis进行遍历序
示例代码见下1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
using namespace std;
const int maxn=310000;
int n,m;
vector<int> M[maxn];//建立图（不带边权）
bool vis[maxn];//每个顶点是否被访问过（dfs的遍历序，规定每个顶点只能访问一次）
void dfs(int x)//深搜，访问一个节点x
{
cout<<x<<" ";//把节点x输出
vis[x]=1;//设置节点x已经被访问
for(int i=0;i<M[x].size();i++)
{
int t=M[x][i];//节点x可以访问到的第i个节点
if(!vis[t])//节点没有被访问
{
dfs(t);
}
}
}
void bfs(int x)//广搜
{
queue<int> Q;//队列中记录访问到哪个节点
vis[x]=1;//记录节点已被访问
Q.push(x);
while(!Q.empty())
{
int hd=Q.front();//调用队列头
cout<<hd<<" ";//队列头出队
for(int i=0;i<M[hd].size();i++)
{
int t=M[hd][i];
if(!vis[t])//节点没有被访问
{
Q.push(t);//压入节点
vis[t]=1;//记录节点已被访问
}
}
Q.pop();//弹出队列
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1,a,b;i<=m;i++)
{
cin>>a>>b;
M[a].push_back(b);//M[a]多了一个元素b
}
for(int i=1;i<=n;i++)
{
sort(M[i].begin(),M[i].end());//对每一个顶点可到的点进行大小排序
// 起始地址 结束地址
}
dfs(1);//dfs
cout<<endl;
for(int i=1;i<=n;i++)
{
vis[i]=0;//清空vis数据
}
bfs(1);//bfs
return 0;
}