C++图论问题：国王巡城期望日期计算

这是一个图论问题，需要使用图的遍历算法来求解。\n\n首先，我们可以使用邻接表来表示图的结构。定义一个vector<vector> adj来存储每个城市与其相邻的城市。\n\n接下来，我们需要计算每个城市的期望。假设城市i的期望为E[i]，那么E[i]可以通过以下方式计算：\n\n1. 如果城市i是首都，那么E[i] = 1，因为国王第一天就会到达首都。\n2. 如果城市i不是首都，那么E[i]可以通过与其相邻的城市的期望来计算。假设城市i与城市j相邻，那么E[i] = (E[j] + 1) / (k + 1)，其中k是与城市j相邻的城市数量（不包括城市i）。\n\n为了计算每个城市的期望，我们可以使用深度优先搜索（DFS）算法。从首都开始，对每个城市进行DFS，计算其期望。\n\n具体实现如下：\n\ncpp\n#include <iostream>\n#include <vector>\nusing namespace std;\n\nconst int MOD = 998244353;\n\nvector<vector<int>> adj;\nvector<int> visited;\nvector<int> expect;\n\nvoid dfs(int city) {\n visited[city] = 1;\n\n // 如果城市是首都，期望为1\n if (city == 1) {\n expect[city] = 1;\n } else {\n int num_adj = adj[city].size(); // 与城市相邻的城市数量\n for (int i = 0; i < num_adj; ++i) {\n int adj_city = adj[city][i];\n if (visited[adj_city] == 0) {\n dfs(adj_city);\n }\n expect[city] = (expect[city] + expect[adj_city] + 1) % MOD;\n }\n }\n}\n\nint main() {\n int n, m;\n cin >> n >> m;\n\n // 初始化邻接表和visited数组\n adj.resize(n + 1);\n visited.resize(n + 1, 0);\n expect.resize(n + 1, 0);\n\n // 读取路径信息，构建邻接表\n for (int i = 0; i < m; ++i) {\n int u, v;\n cin >> u >> v;\n adj[u].push_back(v);\n adj[v].push_back(u);\n }\n\n // 从首都开始进行DFS\n dfs(1);\n\n // 输出每个城市的期望\n for (int i = 1; i <= n; ++i) {\n cout << expect[i] << " ";\n }\n cout << endl;\n\n return 0;\n}\n\n\n时间复杂度分析：该算法使用了深度优先搜索，时间复杂度为O(n+m)，其中n为城市数，m为路径数。空间复杂度为O(n)，用于存储邻接表和visited数组。