A. How Many Friends Will Be Together With You
One day dandelion and her friends decides to play outside. As there are so many people , they decide to divide into several parts . Dandelion wants to know how many friends will be together with her. The way they use to divide is : everyone can choose one people to join in her group, Such as if A chooses B to join in her group , then B will leave the group she is in now , and joins in the group that A is in . One can also choose some people who has already in her group. All of dandelion抯 friends are expressed as an integer 2,3… n and dandelion is expressed as 1.The choosing work begins from dandelion then the friend who are signed as 2 ?until the friend who are signed as n . Input Each case begins with an integer n, (0
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<string> #include<queue> using namespace std; int num[1000010], id[1000010], sum[1000010]; int main() { int i, j, k, n; while (~scanf("%d",&n)) { for (i = 1; i <= n;i++ ) { scanf("%d", &num[i]); id[i] = i, sum[i] = 1; } for (i = 1; i <= n; i++) { if (id[i] == id[num[i]]) continue; sum[id[i]]++; sum[id[num[i]]]--; id[num[i]] = id[i]; } printf("%d\n", sum[id[1]] - 1); } return 0; }