首页 > 试题广场 >

谍中谍中谍中谍中谍...

[编程题]谍中谍中谍中谍中谍...
  • 热度指数：419 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}在一所学校里，如果老师发现学生有恶作剧行为，就会给该生进行一次退学警告。今天老师抓住了 n 名学生（编号 1\sim n）参与恶作剧。
\hspace{15pt}老师先随机逮到某位学生并给该生进行一次退学警告。随后按照被抓学生的"供述"继续抓下一位：若老师刚刚抓到的是学生 x ，他会指认真正的带头人是学生 p_x ，于是老师去抓 p_x 并给该生进行一次退学警告。如此反复，由于学生数量有限，过程最终会第一次出现给一个已经被退学警告过的学生进行一次退学警告的情况，此时这个学生就会被老师劝说进行自愿退学，随后老师才会解气并停下来。
\hspace{15pt}你不知道老师最初抓到的是哪位学生，但你知道所有的指认关系 p_1,p_2,\dots ,p_n。对于每个可能的首位学生 a ，请输出最后被老师劝说进行自愿退学的那名学生的编号。

【名词解释】
\hspace{15pt}指认关系：学生 i 指认的学生 p_i 被视为一条有向边 i\to p_i，因此所有学生构成一张每个点出度为 1 的有向图。

输入描述:
\hspace{15pt}第一行输入一个整数 n\left(1\leqq n\leqq 1000\right)——参与恶作剧的学生人数。 
\hspace{15pt}第二行输入 n 个整数 p_1,p_2,\dots ,p_n\left(1\leqq p_i\leqq n\right)，其中 p_i 表示被学生 i 指认的学生编号。


输出描述:
\hspace{15pt}输出一行共 n 个整数，第 a 个整数表示当老师最先抓到学生 a 时，最后被老师劝说进行自愿退学的学生编号。
示例1

输入

3
2 3 1

输出

1 2 3

说明

以学生 1 为起点：抓 1\,(\text{警告})\rightarrow2\,(\text{警告})\rightarrow3\,(\text{警告})\rightarrow1\,(\text{退学})，此时学生 1 被老师劝说自愿退学；其余起点同理，可验证输出正确。
算法知识视频讲解
添加回答
C
孤独的红烧排骨头像 孤独的红烧排骨
#include <stdio.h>

int main() {
   int n;
   scanf("%d",&n);
   int duiying[n+1];
   for(int i=1;i<=n;i++)
   {
    scanf("%d",&duiying[i]);
   
   }

for(int i=1;i<=n;i++)
{int cishu[1001]={0};
cishu[i]++;
int t=i;
while(1)
{
cishu[duiying[t]]++;
if(cishu[duiying[t]]==2)
{
    printf("%d ",duiying[t]);
    break;
}
t=duiying[t];
}

}



    return 0;
}
发表于 2026-02-09 19:03:00 回复(0)
提交观点

问题信息

难度：
1条回答 107浏览

热门推荐

相关试题

谍中谍中谍中谍中谍...

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号