C++U6-01-阶段测评练习

只需按照题目。分开跑dfs和bfs，需要注意初始化vis数组。

#include<bits/stdc++.h>
using namespace std;

int a[1005][1005];  //邻接矩阵 
int vis[1005];      //标记是否被访问 
int n,m;

void dfs(int cur){
    vis[cur] = 1;
    cout << cur << ' ';
    for(int i = 1;i <= n;i++){
        if(!vis[i] && a[cur][i]) { //若未被访问且存在路径，可以搜索 
            dfs(i);
        } 
    }
}

void bfs(int cur){
    queue<int> q;
    q.push(cur);
    vis[cur] = 1;
    cout << cur << ' ';
    while(!q.empty()) {
        int head = q.front();
        for(int i = 1;i <= n;i++){
            if(!vis[i] && a[head][i]) {  //若未被访问且存在路径，可以搜索
                vis[i] = 1;
                cout << i << ' ';
                q.push(i);
            } 
        }
        q.pop();
    }
}

int main(){
    cin >> n >> m;
    for(int i = 0;i < m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        a[x][y] = 1;
    } 
    dfs(1);
    cout << '\n';
    memset(vis,0,sizeof vis); //重新进行搜索，需要初始化vis数组 
    bfs(1);
    return 0;
}

要得到每个点能达到的编号最大的点，只需要对每个点单独计算一遍答案。对每个点作为起点遍历这张图，不妨考虑dfs，这样每次复杂度就是O(n+m) .最终复杂度O(nm)

#include<bits/stdc++.h>
using namespace std;

int a[1005][1005];  //邻接矩阵 
int ans[1005];      //存储答案，表示i的最大能访问点 
int vis[1005];      //标记是否被访问 
int n,m;

void dfs(int x,int cur){  //第一维表示起点，第二维表示当前点 
    vis[cur] = 1; 
    ans[x] = max(ans[x],cur);    //维护答案 
    for(int i = 1;i <= n;i++){
        if(!vis[i] && a[cur][i]) {
            dfs(x,i);
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        a[x][y] = 1;
    }
    for(int i = 1;i <= n;i++){
        memset(vis,0,sizeof vis);  //每次重新dfs，所以需要初始化 
        dfs(i,i);
    }
    for(int i = 1;i <= n;i++)
        printf("%d ",ans[i]);
    return 0;
}

可以用一个数组记录该点能够被多少个小马访问。所以可以让每个小马从对应的起点开始遍历整张图，使用dfs算法，如果最终sum == k.说明这个点满足条件

#include<bits/stdc++.h>
using namespace std;

int a[505][505];  //邻接矩阵 
int b[105];            //存储小马所在位置
int sum[505];      //餐馆能够被访问的次数
int vis[505];      //标记是否被访问 
int n,m;

void dfs(int cur){
    sum[cur]++;
    vis[cur] = 1;
    for(int i = 1;i <= n;i++){
        if(!vis[i] && a[cur][i]) {    //若未被访问且存在路径，可以搜索 
            dfs(i);
        } 
    }
}

int main(){
    int k;
    cin >> k >> n >> m;
    for(int i = 1;i <= k;i++){
        cin >> b[i];
    } 
    for(int i = 1;i <= m;i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        a[x][y] = 1;
    }
    for(int i = 1;i <= k;i++){
        memset(vis,0,sizeof vis);   //每次都要重新搜索，需要初始化 
        dfs(b[i]);
    }
    int ans = 0;
    for(int i = 1;i <= n;i++){
        if(sum[i] == k) ans++;   //仅当所有马都能到达，才能就餐 
    }
    cout << ans;
    return 0;
}