有 � n 个小朋友(编号依次为 1 , 2 , … , � 1,2,…,n)要排队。 一开始他们各自为一队,接下来,老师会发布 � m ( ≤ 1000 ≤1000)条命令,每条命令给出两个同学的编号 � , � i,j,表示让 � j 同学排到 � i 同学后面。原先在 � j 后面的同学则保持原来的队伍不变。 输出完成老师的 � m 条指令以后,还剩下多少列队伍,并按照队首同学编号从小到大的顺序输出每个队伍,输出一个队伍时,按照从前到后的顺序输出队伍中每个同学的编号。用c++写代码
时间: 2024-02-13 09:04:13 浏览: 19
好的,以下是完整的 C++ 代码实现:
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
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;
}
}
struct Queue {
int head, tail;
int members[MAXN];
bool operator<(const Queue& q) const {
return head < q.head;
}
} queues[MAXN];
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;
for (int i = 1; i <= n; i++) {
int f = find(i);
if (team[i] == i) {
queues[cnt].head = i;
queues[cnt].tail = i;
queues[cnt].members[0] = i;
cnt++;
} else {
queues[f].members[++queues[f].tail - queues[f].head] = i;
}
}
sort(queues, queues + cnt);
cout << cnt << endl;
for (int i = 0; i < cnt; i++) {
cout << queues[i].members[0];
for (int j = 1; j <= queues[i].tail - queues[i].head + 1; j++) {
cout << " " << queues[i].members[j];
}
cout << endl;
}
return 0;
}
```
和之前的代码不同,这里我们定义了一个结构体 `Queue` 来表示队伍。每个 `Queue` 有两个成员变量 `head` 和 `tail` 分别表示队首和队尾,以及一个数组 `members` 表示队伍中的所有小朋友编号。注意,为了方便起见,我们在 `members` 数组中存储的是相对于队首的偏移量,而不是绝对编号。
在处理完所有命令后,我们遍历一遍 `team` 数组,将每个小朋友所在的队伍添加到对应的 `Queue` 中。具体来说,如果该小朋友所在的队伍还没有被添加过,我们新建一个 `Queue`,将其添加到队列数组中,并将该小朋友的编号存储在 `members[0]` 中;否则我们将该小朋友的编号存储在对应的 `Queue` 的 `members` 数组中。
最后,我们对所有队伍按照队首编号从小到大排序,然后依次输出每个队伍的所有小朋友。注意,在输出每个小朋友编号时,我们需要将相对编号转化为绝对编号。