某 E 正在机房值班,小朋友吵得她头晕脑胀,她将 N 名吵闹的小朋友带出了机房,依次编号为 1,2,⋯,N。 某 E 发现,这些小朋友形成了若干个小团伙,每个小朋友属于且只属于一个小团伙。她要求每一名小朋友指出自己所在小团伙的首领编号,第 i 名小朋友指认的首领编号为 Si 。 假定所有小朋友都没有说谎,请问这 N 名小朋友中一共形成了多少个小团伙? 输入格式 输入共两行。 输入的第一行为一个正整数 N。 输入的第二行为 N 个正整数,第 i个为 Si 输出格式 输出一行一个整数,代表机房里小团体的数目。 用C语言写
时间: 2024-04-16 15:25:41 浏览: 107
基于微信小程序的设备机房报修小程序V4.1设计源码
5星 · 资源好评率100%
对于这个问题,可以使用并查集来解决。首先每个小朋友的首领为自己,然后根据小朋友的指认关系进行合并操作。最后统计有多少个不同的首领即可。
以下是用C语言实现的代码:
```c
#include <stdio.h>
#define MAXN 100000
int leader[MAXN + 1];
int findLeader(int x) {
if (leader[x] == x) {
return x;
} else {
return leader[x] = findLeader(leader[x]);
}
}
void merge(int x, int y) {
int leaderX = findLeader(x);
int leaderY = findLeader(y);
if (leaderX != leaderY) {
leader[leaderY] = leaderX;
}
}
int main() {
int N;
scanf("%d", &N);
// 初始化每个小朋友的首领为自己
for (int i = 1; i <= N; i++) {
leader[i] = i;
}
for (int i = 1; i <= N; i++) {
int Si;
scanf("%d", &Si);
// 合并操作
merge(i, Si);
}
int count = 0;
for (int i = 1; i <= N; i++) {
if (leader[i] == i) {
count++;
}
}
printf("%d\n", count);
return 0;
}
```
希望能帮到你!
阅读全文