现在有 � n 个小朋友(编号依次为 1 , 2 , … , � 1,2,…,n)要排队。 一开始他们各自为一队,接下来,老师会发布 � m ( ≤ 1000 ≤1000)条命令,每条命令给出两个同学的编号 � , � i,j,表示让 � j 同学排到 � i 同学后面。原先在 � j 后面的同学则保持原来的队伍不变。 输出完成老师的 � m 条指令以后,还剩下多少列队伍,并按照队首同学编号从小到大的顺序输出每个队伍,输出一个队伍时,按照从前到后的顺序输出队伍中每个同学的编号。
时间: 2024-02-13 19:04:12 浏览: 232
好的,以下是完整的 C++ 代码实现:
```cpp
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1005;
int n, m;
int team[MAXN];
int find(int x) {
if (team[x] == x) return x;
return team[x] = find(team[x]);
}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) {
team[fy] = fx;
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
team[i] = i;
}
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
merge(x, y);
}
int cnt = 0;
bool vis[MAXN];
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; i++) {
int f = find(i);
if (!vis[f]) {
cnt++;
vis[f] = true;
}
}
cout << cnt << endl;
for (int i = 1; i <= n; i++) {
int f = find(i);
if (vis[f]) {
vis[f] = false;
cout << i;
for (int j = i + 1; j <= n; j++) {
if (find(j) == f) {
cout << " " << j;
}
}
cout << endl;
}
}
return 0;
}
```
这里我们同样使用了一个数组 `team` 来记录每个小朋友所在的队伍编号。我们使用 `find` 函数来查找某个小朋友所在的队伍,使用 `merge` 函数来合并两个队伍。
在输出答案时,我们使用了一个 `vis` 数组来记录每个队伍是否已经被输出过,避免重复输出。对于每个队伍,我们先输出队首编号,然后遍历一遍数组,输出所有属于该队伍的小朋友编号。
注意,题目中要求按照队首编号从小到大的顺序输出每个队伍,因此我们在遍历 `team` 数组时需要先将所有队伍按照队首编号从小到大排序。
另外,题目中给出的编号是从 1 开始的,因此数组下标也需要从 1 开始。
阅读全文