排队问题 - C++代码实现/n/n## 题目描述/n/n现在有 $n$ 个小朋友（编号依次为 $1, 2, /dots, n$）要排队。/n一开始他们各自为一队，接下来，老师会发布 $m$ （$//le 1000$）条命令，每条命令给出两个同学的编号 $i, j$，表示让 $j$ 同学排到 $i$ 同学后面。原先在 $j$ 后面的同学则保持原来的队伍不变。/n输出完成老师的 $m$ 条指令以后，还剩下多少列队伍，并按照队首同学编号从小到大的顺序输出每个队伍，输出一个队伍时，按照从前到后的顺序输出队伍中每个同学的编号。/n/n## 输入格式/n/n从标准输入读入数据。/n第一行，两个整数 $n,m$（$1//le n,m //le 1000$）。/n接下来 $m$ 行，每行两个整数 $i,j$ （$1 //le i,j //le n$，$i //ne j$），表示让 $j$ 同学排到 $i$ 同学后面。/n/n## 输出格式/n/n输出到标准输出。/n输出若干行。/n第一行，一个整数 $k$ ，表示执行完操作后的队伍数量。/n接下来 $k$ 行，按照队首同学编号从小到大的顺序输出每个队伍。每行输出一个队伍，输出一个队伍时，按照从前到后的顺序输出队伍中每个同学的编号。/n/n## 样例 #1/n/n### 样例输入 #1/n/n/n5 5/n3 5/n4 2/n5 4/n5 4/n2 4/n/n/n### 样例输出 #1/n/n/n3/n1 /n2 4 /n3 5/n/n/n## C++ 代码实现/n/ncpp/n#include <iostream>/n#include <vector>/n/nusing namespace std;/n/nint main() {/n int n, m;/n cin >> n >> m;/n/n vector<int> next(n + 1, -1); // 记录每个同学后面的同学编号/n vector<int> head(n + 1); // 记录每个队伍的队首编号/n vector<int> tail(n + 1); // 记录每个队伍的队尾编号/n/n for (int i = 1; i <= n; i++) {/n head[i] = tail[i] = i; // 初始化每个同学单独为一队/n }/n/n for (int i = 0; i < m; i++) {/n int x, y;/n cin >> x >> y;/n/n next[tail[x]] = y; // 将y同学排在x同学后面/n tail[x] = tail[y]; // 更新x队伍的队尾为y队伍的队尾/n/n int cur = y;/n while (next[cur] != -1) {/n cur = next[cur]; // 找到y队伍的队尾/n }/n tail[y] = cur; // 更新y队伍的队尾/n }/n/n int count = 0;/n for (int i = 1; i <= n; i++) {/n if (head[i] != -1) {/n count++;/n }/n }/n/n cout << count << endl;/n for (int i = 1; i <= n; i++) {/n if (head[i] != -1) {/n int cur = head[i];/n while (cur != -1) {/n cout << cur << /' /';/n cur = next[cur];/n }/n cout << endl;/n }/n }/n/n return 0;/n}/n/n/n代码解释:/n/n* next 数组：存储每个同学后面的同学编号，-1 表示没有后面的同学。/n* head 数组：存储每个队伍的队首编号，-1 表示该队伍不存在。/n* tail 数组：存储每个队伍的队尾编号。/n/n算法流程：/n/n1. 初始化：将每个同学单独作为一队，并将 next 数组初始化为 -1。/n2. 处理指令：对于每条指令 (x, y)，将 y 同学排到 x 同学后面，更新 next、tail 数组，并找到 y 队伍的队尾。/n3. 统计队伍数量：遍历 head 数组，统计队伍数量。/n4. 输出队伍：遍历 head 数组，找到队伍首并输出该队伍的所有成员。/n/n代码的关键部分：/n/n* next[tail[x]] = y; 将 y 同学排在 x 同学后面。/n* tail[x] = tail[y]; 更新 x 队伍的队尾。/n* while (next[cur] != -1) { cur = next[cur]; } 找到 y 队伍的队尾。/n* tail[y] = cur; 更新 y 队伍的队尾。/n/n代码的优点:/n/n* 代码清晰简洁，易于理解。/n* 时间复杂度为 $O(n + m)$，空间复杂度为 $O(n)$。/n/n代码的局限性:/n/n* 只能处理 $n$ 和 $m$ 都小于等于 1000 的数据。/n/n优化建议:/n/n* 可以使用并查集来优化代码，将时间复杂度降到 $O(m /alpha(n))$。/n* 可以使用链表来存储队伍，避免使用 next 数组，从而降低空间复杂度。/n/n总结:/n/n本代码实现了排队问题的解决方案，代码清晰简洁，易于理解，并提供了优化建议。