排队问题：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/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);/n vector<int> head(n + 1);/n vector<int> tail(n + 1);/n/n for (int i = 1; i <= n; i++) {/n next[i] = i;/n head[i] = i;/n tail[i] = i;/n }/n/n for (int i = 0; i < m; i++) {/n int a, b;/n cin >> a >> b;/n/n if (tail[a] == tail[b]) {/n continue;/n }/n/n int p = tail[a];/n while (p != b) {/n next[p] = head[b];/n p = next[p];/n }/n/n next[tail[a]] = tail[b];/n tail[a] = tail[b];/n head[b] = head[a];/n }/n/n vector<vector<int>> result;/n for (int i = 1; i <= n; i++) {/n if (head[i] == i) {/n vector<int> team;/n int p = i;/n while (p != n + 1) {/n team.push_back(p);/n p = next[p];/n }/n result.push_back(team);/n }/n }/n/n cout << result.size() << endl;/n for (const auto& team : result) {/n for (const auto& member : team) {/n cout << member << /' /';/n }/n cout << endl;/n }/n/n return 0;/n}/n/n/n## 代码解释/n/n* next[i]：表示编号为 i 的小朋友后面是谁，如果没有则为 i 本身。/n* head[i]：表示编号为 i 的小朋友所在队伍的队首是谁，如果 i 是队首，则 head[i] = i。/n* tail[i]：表示编号为 i 的小朋友所在队伍的队尾是谁，如果 i 是队尾，则 tail[i] = i。/n/n代码逻辑：/n1. 初始化数组，每个小朋友都是独立的队伍。/n2. 遍历每个指令，将 j 放在 i 后面。/n3. 遍历 i 的队尾到 j，将 next 指针指向 j 的队首。/n4. 将 i 的队尾指向 j 的队尾，并将 j 的队首指向 i 的队首。/n5. 遍历每个小朋友，如果 head[i] = i，则说明 i 是队首，将 i 所在的队伍添加到结果列表中。/n/n本代码使用了循环链表的思想来维护队伍，方便地进行队伍合并操作。/n/n希望以上解释能够帮助您更好地理解代码，如果您有任何问题，请随时提出。/n