P5318 【深基18.例3】查找文献

题目

解题思路

重点有两点：

1. 使用vector建立无权有向图，并使用迭代器对图排序
2. 深搜，访问节点，使用vis进行遍历序

示例代码见下

#include<bits/stdc++.h>
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;
}