我不想当组长

简要题面

题面

众所周知，老师们都热衷于分组学习，这一天芳芳来到了一个有n位同学的新班级，每位同学都有一个独一无二的序号，从1到n，毫无意外，这个班的老师也要求分组学习。

每个人都想和自己最好的朋友在同一个小组，善良的老师愿意满足每个人的小心愿，所以老师让每一位同学把自己最好的朋友的序号写在纸上按顺序交给她。分完组后老师发现没有人愿意当小组长，于是决定让每一组序号最小的同学担任小组长。

这一天，老师照常的走进教室，拿出她的小组长名单准备了解每一组的学习情况，但她突然发现名单不见了。老师在包里翻找了半天，最后只找到了写着每一位同学最好的朋友序号的小纸条，幸运的是纸条的顺序还没有被打乱，最上方的纸条是1号同学写的，最下方的纸条是n号同学写的。

为了不让同学们发现老师弄丢了小组长名单，她需要在上课之前根据纸条上的信息找到所有的小组长，你可以帮帮她吗？

输入描述

第一行输入n，表示学生人数

接下来n行每行一个数字，表示每位同学最好的朋友的序号

输出描述

按序号从小到大输出所有小组长的序号，每行一个序号

输入输出样例

输入 #1

5
5 3 2 1 4

输出 #1

1
2

说明/提示

解法

参考程序

#include<bits/stdc++.h>
using namespace std;
int fa[100005];
int find(int x){
    if(x!=fa[x]) return fa[x]=find(fa[x]);
    return x;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    for(int i=1;i<=n;i++){
        int temp;
        cin>>temp;
        int ni=find(i),nt=find(temp);
        if(ni!=nt){
            if(ni<nt) fa[nt]=ni;
            else fa[ni]=nt;
        }
    }
    for(int i=1;i<=n;i++){
        if(i==find(i)) cout<<i<<'\n';
    }
    return 0;
}