【2024东区信息学小学组】4.旅行（tour）

Question

描述

由于在某谷上举办的比赛反响热烈，参与人数众多，Jimmy 得到了一笔客观的广告费！于是，他决定来一场“说走就走的旅行”。
Jimmy 一共有 N 座想去的小岛，编号为 1 ~ N 。小岛之间一共有 M 班轮船，其中第 i 班轮船可以带 Jimmy 从第 xi 个小岛去第 yi 个小岛，但是 Jimmy 搭不了回程的轮船，因此他不能坐第 i 班轮船从第 yi 个小岛回到第 xi 个小岛。
在去之前 Jimmy 想做一个旅行计划。他可以选择从某个小岛开始旅行，途中搭船经过若干个其他的小岛（也可以不经过其他小岛），最后到达某个小岛并结束旅行。当然，Jimmy也可以选择在一个小岛上一直度假，因此他的旅行可以在同一个岛上开始和结束。Jimmy只关心旅行在哪开始以及在哪结束。他觉得，如果一个旅行计划的开始小岛或者结束小岛与其他的计划不同，那么这两个计划就算是不同的。
Jimmy 现在想知道他一共有多少种不同的旅行计划。你能帮他吗？

输入描述

第一行两个正整数 N, M ，分别表示小岛的数量，以及轮船的班数。
接下来的 M 行，每行两个正整数 xi, yi，表示第 i 班轮船可以从第 xi 个小岛去到第 yi
个小岛。

输出描述

一行一个整数，表示不同的旅行计划种数。

用例输入 1

3 3
1 2
2 3
3 2
用例输出 1

7
用例输入 2

3 0
用例输出 2

3
用例输入 3

4 4
1 2
2 3
3 4
4 1
用例输出 3

16
提示

【样例 1 解释】
一共有 7 种不同的旅行计划，分别为 (1,1), (1,2), (1,3), (2,2), (2,3), (3,2)
, (3,3)，其中 (p,q) 表示 Jimmy 从第 p 个小岛开始旅行，在第 q 个小岛结束。
注意，由于 Jimmy 无法从第 2 个小岛前去第 1 个小岛，因此不存在 (2,1) 这种旅行方
案。同理，也不存在 (3,1) 这种旅行方案。

【样例 2 解释】
Jimmy 没有任何轮船可以搭，他只能在同一个小岛上开始和结束旅行，一共有 3 个小岛，因此一共有 3 种不同的旅行方案。

【样例 3 解释】
Jimmy 可以在任意小岛上开始旅行、并在任意小岛上结束旅行，因此总的旅行方案数为
4 × 4 = 16 种。
【测试点约束】
对于 100% 的数据，满足：
•1 ≤ N ≤ 2000
•0 ≤ M ≤ 2000
•1 ≤ xi, yi ≤ N
•xi ̸= yi
•保证不存在完全相同的轮船班次，即 (xi, yi) 必定互不相同

Answer 1

阿里嘎多学长整理AIGC生成，因移动端显示问题导致当前答案未能完全显示，请使用PC端查看更加详细的解答过程

问题描述

Jimmy 获得了一笔广告费，决定来一场“说走就走的旅行”，他有 N 座想去的小岛，编号为 1 ~ N。小岛之间一共有 M 条路，可以从一个小岛到另一个小岛。Jimmy 想知道他可以访问的最多的小岛数量。

解决方案

可以使用深度优先搜索（DFS）或广度优先搜索（BFS）算法来解决这个问题。下面是一个使用 DFS 算法的 C++ 代码示例：

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAX_N = 1000;
const int MAX_M = 10000;

int N, M;
vector<vector<int>> graph(MAX_N);
vector<bool> visited(MAX_N, false);

int dfs(int node) {
    visited[node] = true;
    int max_nodes = 1;
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            max_nodes += dfs(neighbor);
        }
    }
    return max_nodes;
}

int main() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    int max_nodes = 0;
    for (int i = 1; i <= N; i++) {
        if (!visited[i]) {
            max_nodes = max(max_nodes, dfs(i));
        }
    }
    cout << max_nodes << endl;
    return 0;
}

说明

在上面的代码中，我们使用了一个 DFS 算法来遍历小岛之间的路。我们使用一个 visited 数组来记录已经访问过的小岛。对于每个小岛，我们遍历它的邻居，如果邻居没有被访问过，我们递归地访问邻居，并将访问的数量加到当前小岛的访问数量中。最后，我们输出访问的最多的小岛数量。