首页 > 试题广场 >

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

[编程题]谍中谍中谍中谍中谍...
  • 热度指数：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 被老师劝说自愿退学；其余起点同理，可验证输出正确。
算法知识视频讲解
开通博客
头像 ikun_ac
发表于 2025-08-09 00:58:05
题目链接 谍中谍中谍中谍中谍.... 题目描述 有 名学生，每名学生 指认一名学生 ，形成一张每点出度为 的有向图。老师从某个起点开始沿着指认关系不断抓下一位，第一次对某个已经被“警告”过的学生再次“警告”时，该学生自愿退学，过程结束。对每个可能的起点 ，求最终退学的学生编号。 输入： 第一 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 小男娘
发表于 2026-02-04 11:16:36
朴素做法：对每一个起点跑一遍，用一个布尔数组记录是否访问过，时间复杂度。优化：找出所有的环，答案为最近的环上点。时间复杂度。 #include <iostream> #include <vector> using namespace std; int n; vector&l 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 丨阿伟丨
发表于 2025-09-01 09:52:15
题目链接 谍中谍中谍中谍中谍.... 题目描述 有 名学生（编号 到 ），每位学生 都会指认一名学生 作为带头人。老师从任意一名学生开始警告，然后根据指认关系一路警告下去，直到第一次遇到一名已经被警告过的学生。这名被重复警告的学生将被劝退。 任务是，对于每个可能的起始学生 （从 到 ），找 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 小胡放轻松
发表于 2025-11-23 23:28:23
/*我的直观想法是用一个数组freq记录学生被抓取的次数，从1到n的循环每次都初始化freq数组元素为0，然后随着指认链向前为freq数组元素赋值，被指认到一次就使得元素值++，一次指认后检查被指认元素的freq值是否> 1，大于1则打印当前学生编号并停止指认循环*/ #include < 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 爱吃鸡腿的小松鼠许愿简历通过
发表于 2025-08-28 22:20:14
import java.util.*; import java.io.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 冷艳的西红柿刷牛客
发表于 2025-11-08 11:46:48
#include <iostream> #include <vector> #include <stack> #include <cstring> #include <set> using namespace std; //图的特点是出度 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 银河护胃队
发表于 2026-02-24 13:54:01
#include<bits/stdc++.h> using namespace std; const int N=1e3+10; int n,p[N]; void solve(){ for(int i=1;i<=n;i++){ vector<bool& 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

难度：
1条回答 109浏览

热门推荐

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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