Atcoder TOYOTA SYSTEMS Programming Contest 2021(AtCoder Beginner Contest 228) B - Takahashi‘s Secret

题目链接：B - Takahashi's Secret (atcoder.jp)

Problem Statement

Takahashi has N friends. They have nicknames: Friend 1, Friend 2, …, Friend N.

One day, Takahashi accidentally let one of his friends, Friend X, learn his shameful secret.
For each i = 1,2,…,N, when Friend ii learns the secret, he/she will share it with Friend Ai​, if Friend Ai​ has not already learned it.

How many of Takahashi's friends will learn the secret in the end?

Constraints

• 2≤N≤105
• 1≤X≤N
• 1≤Ai​≤N
• Ai​!=i
• All values in input are integers.

---

Input

Input is given from Standard Input in the following format:

N X
A1​ A2​ ... AN​

Output

Print the answer.

---

Sample Input 1 Copy

4 2
3 1 1 2

Sample Output 1 Copy

3

Takahashi's secret will be learned by Friend 1, Friend 2, and Friend 3, as follows.

• One day, Takahashi let Friend 2 learn the secret.
• Friend 2 shares it with Friend 1.
• Friend 1 shares it with Friend 3.

In the end, three of his friends learn the secret, so we print 33.

---

Sample Input 2 Copy

20 12
7 11 10 1 7 20 14 2 17 3 2 5 19 20 8 14 18 2 10 10

Sample Output 2 Copy

7

题意：你有n个朋友，每个朋友都会把秘密告诉a【i】，你把密码告诉x，求最后会有多少人知道秘密。

思路：可以通过搜索或者循环去查找x会把秘密告诉多少人，由于a【i】 是1-n的，那么朋友圈肯定会有循环节，当朋友被多次告知的时候，搜索结束（循环结束）

#include<bits/stdc++.h>
using namespace std;

int arr[100005];
bool vis[100005];
int ans = 0;

void dfs(int x){
	if(vis[arr[x]] == 0){
		ans++;
		vis[arr[x]] = 1;
		dfs(arr[x]);
	}
}

int main(){
	int n, x;
	while(cin >> n >> x){
		for(int i = 1; i <= n; i++){
			cin >> arr[i];
			vis[i] = 0;
		}
		ans = 1;
		vis[x] = 1;
		dfs(x);
		
		cout << ans << endl;
	}
	/*
		循环的写法：
		int n, x;
		while(cin >> n >> x){
			for(int i = 1; i <= n; i++){
				cin >> arr[i];
				vis[i] = 0;
			}
			int ans = 0;
			while(vis[x] == 0){
				ans++;
				vis[x] = 1;
				x = arr[x];
			}
			cout << ans << endl;
		}
		
		*/
	return 0;
}