算法设计与分析复习（第4章 蛮力法）

7-1 h0117. 完全数

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        int sum = 0;
        for (int i = 1; i <= sqrt(x); i++) 
            if (x % i == 0) 
                if(x / i != i) sum += i + x / i;
                else sum += i;
        
        if (sum - x == x) printf("%d is perfect\n", x);
        else printf("%d is not perfect\n", x);
    }

    return 0;
}

7-2 h0052. 完美立方

#include<stdio.h>
int main()
{
    int N;
    scanf("%d", &N);
    for(int a = 2; a <= N; a++)
    {
        for(int b = 2; b<= a; b++)
        {
            for(int c = b; c<= a; c++)
            {
                for(int d = c; d<= a; d++)
                {
                    if(a*a*a == b*b*b + c*c*c + d*d*d)
                    {
                        printf("Cube = %d, Triple = (%d,%d,%d)\n", a, b, c, d);
                    }
                }
            }
        }
    }
    return 0;
}

7-3 h0029. 数组排序

#include <stdio.h>
#include <string.h>
//从小到大排序
void sort(int a[], int l, int r)
{
    int i, j, temp;
    for (i = l;i < r; i++)
        for (j = i + 1; j <= r; j++)
            if (a[i] > a[j])
            {
                temp = a[i]; a[i] = a[j]; a[j] = temp;
            }
}
 
int main()
{
    int n, l, r, i;
    scanf("%d %d %d", &n, &l, &r);
    int a[n];
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    sort(a, l, r);
    for (i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

7-4 h0364. 双指针1

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+10;
long long int a[N];
int main()
{
    long long int n,p;
    cin>>n>>p;
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    int res=0;
    for(int i=0,j=0;i<n;i++)
    {
        while(j<n&&a[i]>a[j]*p) j++;
        res=max(res,i-j+1);
    }
    cout<<res;
    return 0;
}

7-5 数列分段

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++) cin>>a[i];
    int count=0;
    for(int i=0;i<n;i++)
    {
        if(a[i]!=a[i+1])
            count+=1;
    }
    cout<<count;
    return 0;
}

7-6 最小差值

#include<cstdio>
#include<vector>
#include<climits>
#include<algorithm>
#include<cmath>
std::vector<int> A;
int main(){
int n, num, ans = INT_MAX;
scanf("%d", &n);
while(n--){
    scanf("%d", &num);
    A.push_back(num);		
}
std::sort(A.begin(), A.end());
for(int i = 1; i < A.size();i++){
    int tempDis = std::abs(A[i] - A[i-1]);
    if(tempDis < ans) ans = tempDis;
}
printf("%d", ans);
return 0;
}

7-7 相邻数对

#include <iostream>
#include <cstring>
const int N = 10000;
bool flag[N+2];
using namespace std;
int main()
{
    int n, v, sum=0;
    // 清除标志：flag[i]为true表示i已经出现过，flag[i]为false表示i尚未出现过
    memset(flag, false, sizeof(flag));

    // 输入数据，进行判断，统计处理
    cin >> n;
    for(int i=1; i<=n; i++) {
        // 输入数据
        cin >> v;
        flag[v] = true;
        // 进行判断和统计处理
        if(flag[v-1])
            sum++;
        if(flag[v+1])
            sum++;
    }
    // 输出结果
    cout << sum << endl;
    return 0;
}

7-8 h0181. 约瑟夫问题

#include<iostream>
using namespace std;
const int MAX = 305;
int main() {
int n, m;
while (cin >> n >> m) {
    if (n == 0 && m == 0) break;
    int arr[MAX] = { 0 };
    for (int i = 1; i <= n; i++) arr[i] = 1;//初始化数组，1未淘汰，0淘汰
    int sum = n, cur = 1, count = 0;//sum记录未淘汰猴数量，cur指向圈内所有猴（包括已经淘汰的），count是报的数
    while (sum > 1) {//不止一只猴时就继续报数淘汰
        if (arr[cur] == 1) {
            count++;//报数
            if (count == m) {//恰好报到m，淘汰该猴
                arr[cur] = 0;
                count = 0;//重新报数
                sum--;//猴数减一
            }
        }
        cur++;
        cur = (cur == n + 1) ? 1 : cur;//cur要循环走，所以指向数组末尾时回到起始
    }
    //循环找最后剩下那只猴
    for (int i = 1; i <= n; i++) {
        if (arr[i] == 1) {
            printf("%d\n", i);//注意输出的是猴的编号
            break;//肯定只有一只猴王，所以输出后直接跳出，争取一点效率。。
        }
    }
}
return 0;
}

7-9 变形约瑟夫问题

#include <iostream>
using namespace std;
int main(){
    int n,k;
    int sum=0,c=0;
    cin>>n>>k;
    int i;
    for(i=1;i<=n;i++){
        sum=k%i;
        c=c+sum;
    }
    cout<<c;
    return 0;
}

7-10 h0279. 逆序对

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int a[100010],b[100010];///b[]临时数组 
ll ans;///记录逆序对数   数据大 易超int 
void merge(int l,int m,int r)
{
    //cout<<l<<" "<<r<<endl;
    int i=l;///左半区域第一个节点地址 
    int j=m+1;///右半区域第一个节点地址 
    int pos=l;///临时数组的下标位置 
    while(i<=m&&j<=r)///在范围内 
    {
        if(a[i]<=a[j]) ///排序进入临时数组 
        {
            b[pos++]=a[i++];
        }
        else
        {
            b[pos++]=a[j++];
            ans+=m-i+1;//i~m 排序好的数 和j 都能构成逆序对 
        }
    }
    while(i<=m)///左半区域还有剩余元素 
    b[pos++]=a[i++];
    while(j<=r)///右半区域还有剩余元素 
    b[pos++]=a[j++];
    for(int i=l;i<=r;i++)///排序后 更新a[]数组l~r 
    a[i]=b[i];
    //cout<<"+"<<a[i]<<" ";
    //cout<<endl; 
}
void merge_sort(int l,int r)///归并 
{
    if(l<r)
    {
        int mid=(l+r)>>1;
        merge_sort(l,mid);
        merge_sort(mid+1,r);
        merge(l,mid,r);
    }
}
int main()
{
    int n;
    cin>>n;
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    merge_sort(1,n);
    cout<<ans<<endl;
    return 0;
}

7-11 h0341. DNA Sorting

#include <iostream>

using namespace std;

char oriList[100][50];    //原始DNA数据
char sortedList[100][50];    //排序后DNA数据
char str[50];
int rpc[100];    //记录逆序对数的数组
int order[100];    //记录顺序的数组

//归并排序并计算逆序对数
int merge (int index, int start, int end) {
    if (start == end) {
        return 0;
    }
    int mid = (start + end) / 2;
    int c1 = merge(index, start, mid);
    int c2 = merge(index, mid + 1, end);
    int i = start;
    int j = mid + 1;
    int count = 0;
    int k = 0;
    while (i <= (mid + 1) && j <= (end + 1)) {
        if (i == (mid + 1)) {
            str[k] = sortedList[index][j];
            k++;
            j++;
            continue;
        } else if (j == (end + 1)) {
            str[k] = sortedList[index][i];
            k++;
            i++;
            continue;
        }
        if (sortedList[index][i] > sortedList[index][j]) {
            str[k] = sortedList[index][j];
            j++;
            k++;
            count += (mid - i + 1);
        } else {
            str[k] = sortedList[index][i];
            i++;
            k++;
        }
    }
    for (k = 0; k < end - start + 1; k++) {
        sortedList[index][start + k] = str[k];
    }
    return c1 + c2 + count;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> oriList[i][j];
            sortedList[i][j] = oriList[i][j];
        }
        order[i] = i;
    }
    for (int i = 0; i < m; i++) {
        rpc[i] = merge(i, 0, n - 1);
    }
    for (int i = 0; i < m; i++) {
        for (int j = i + 1; j < m; j++) {
            if (rpc[i] > rpc[j]) {
                int temp = rpc[i];
                rpc[i] = rpc[j];
                rpc[j] = temp;
                temp = order[i];
                order[i] = order[j];
                order[j] = temp;
            }
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cout << oriList[order[i]][j];
        }
        cout << endl;
    }
    return 0;
}

7-12 最大子列和问题

#include<stdio.h>

int main(){
int i,a[100001],b[100001],n;
int maxsum,tempsum=0;

scanf("%d\n",&n);
for(i=0;i<n;i++){
    scanf("%d",&a[i]);
    //if(i!=n-1)scanf(" ");
}
maxsum = 0;
for(i=0;i<n;i++){
    tempsum += a[i];
    if(tempsum < 0) tempsum = 0;		//如果序列中所有整数皆为负数，则输出0
    if(tempsum > maxsum)maxsum = tempsum;
}

printf("%d",maxsum);
return 0;
}

7-13 字符串匹配算法比较

#include <stdio.h>
#include <string.h> 
#include <stdlib.h>
  
typedef int Position;
#define NotFound -1
  
void BuildMatch( char *pattern, int *match )
{
    Position i, j;
    int m = strlen(pattern);
    match[0] = -1;
      
    for ( j=1; j<m; j++ ) {
        i = match[j-1];
        while ( (i>=0) && (pattern[i+1]!=pattern[j]) )
            i = match[i];
        if ( pattern[i+1]==pattern[j] )
             match[j] = i+1;
        else match[j] = -1;
    }
}
  
Position KMP( char *string, char *pattern )
{
    int n = strlen(string);
    int m = strlen(pattern);
    Position s, p, *match;
      
    if ( n < m ) return NotFound;
    match = (Position *)malloc(sizeof(Position) * m);
    BuildMatch(pattern, match);
    s = p = 0;
    while ( s<n && p<m ) {
        if ( string[s]==pattern[p] ) {
            s++; p++;
        }
        else if (p>0) p = match[p-1]+1;
        else s++;
    }
    return ( p==m )? (s-m) : NotFound;
}
int main() {
  char string[1000001] = {0};
  char pattern[1000001] = {0};
  scanf("%s\n", (char *)&string);
  int n;
  scanf("%d", &n);
  for(int i=0; i<n; i++) {
    scanf("%s\n", (char *)&pattern);
    Position p = KMP(string, pattern);
    if(p != NotFound) {
      if(i == n - 1) {
        printf("%s", (char *)string+p);
      } else {
        printf("%s\n", (char *)string+p);
      }
    } else {
      if(i == n - 1) {
        printf("Not Found");
      } else {
        printf("Not Found\n");
      }
    }
  }
  return 0;
}

7-14 字符串匹配（没有代码）

7-15 h0173. 01背包问题

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m,v,w,i,j,a[1005]={0};
    cin>>n>>m;
    for(i=0;i<n;i++){
        cin>>v>>w;
        for(j=m;j>=v;j--)
            a[j]=max(a[j],(a[j-v]+w));
    }
    cout<<a[m];
    return 0;
} 

7-16 h0193. 排列

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    string str = "";
    for (int i = 1; i <= n; i++) {
        str += (i + '0');
    } 
    do {
        // 输出每个字符后加一个空格
        for (int i = 0; i < str.size(); i++) {
            cout << str[i] << " ";
        }
        cout << endl;
    } while (next_permutation(str.begin(), str.end()));
    return 0;
}

7-17 h0145. 会议安排

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

struct meet{
int s,e;//开始和结束时间
}a[10000];

bool cmp(meet a,meet b){
return a.e<b.e;
}//返回先结束的

int main()
{
    int n;//表示共几组数据
    int x;
    cin>>n;
    while(n--)
    {
        cin>>x;//几个会议
        int i;
        for(i=1; i<=x; i++){
            scanf("%d%d",&a[i].s,&a[i].e);
        }//a[0]不放，使得下标从1开始
        a[0].s=-1;a[0].e=-1;
        sort(a+1,a+1+x,cmp);//排序
        int num=1;//会议计数，第一个会议一定在
       int j=1;//第一个会议的下标
        for(i=2;i<=x;i++){
            if(a[i].s>=a[j].e){
                num++;
                j=i;
            }//当下一个的会议开始时间比前一个结束时间要晚，则安排此会议
        }
        cout<<num<<endl;
        }
        return 0;
}

7-18 h0119. 递归实现组合型枚举

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

int n,m;
vector<int> num;

void dfs(int k)
{
    //如题解所述
    if(num.size() > m || num.size() + (n - k + 1) < m)
        return;
    //到达枚举边界，输出结果并结束
    if(k == n + 1)
    {
        for(int i = 0;i < num.size();++i)
            cout << num[i] << " ";

        cout << endl;
        return;
    }

    //选择这个数
    num.push_back(k);
    dfs(k+1);
    //回溯
    num.pop_back();

    //不选择这个数
    dfs(k+1);
}

int main(void)
{
    cin >> n >> m;

    dfs(1);

    return 0;
}

7-19 h0120. 递归实现排列型枚举

#include<stdio.h>
int a[10],book[10]={0};
int n;
void dfs(int x)
{
int i;
if(x>n)
{
    for(i=1;i<=n;i++)
        printf("%d ",a[i]);
    printf("\n");
    return;
}
for(i=1;i<=n;i++)
{
    if(!book[i])
    {
        book[i]=1;a[x]=i;
        dfs(x+1);
        book[i]=0;
    }
}
}
int main()
{
int i;
while(scanf("%d",&n)!=EOF)
{
    dfs(1);
}
return 0;
}

7-20 h0111. 简单的加法（没有代码）

7-21 根据后序和中序遍历输出前序遍历

#include<stdio.h>
 
void dfs(int n,int *last,int *in)
{
    if(n!=0)
    {
        printf(" %d",last[n-1]);
        int i;
        for(i=0; i<n; i++)
            if(in[i]==last[n-1])
                break;
        dfs(i,last,in);
        dfs(n-1-i,last+i,in+i+1);
    }
}
 
int main()
{
    int n;
    scanf("%d",&n);
    int last[n],in[n];
    for(int i=0; i<n; i++)
        scanf("%d",&last[i]);
    for(int i=0; i<n; i++)
        scanf("%d",&in[i]);
 
    printf("Preorder:");
    dfs(n,last,in);
    return 0;
}

7-22 树的遍历

#include<stdio.h>
#include<malloc.h>
int N = 0;
int PreOrder[33] = { '\0' };//中序
int PostOrder[33] = { '\0' };//后序
typedef struct node {
    int num;
    struct node* left;
    struct node* right;
}node;
struct node *create(int pos[], int pre[], int n);
void sequence(node *T);//层序排序输出
int main(void)
{	
    node *T = NULL;//构建二叉树
    scanf("%d", &N);
    int i = 0;
    for (i = 0; i < N; i++)
        scanf("%d", &PostOrder[i]);
    for (i = 0; i < N; i++)
        scanf("%d", &PreOrder[i]);
    T = create(PostOrder, PreOrder, N);
    sequence(T);
    return 0;
}
void sequence(node *T)
{
    struct node *p[33], *q;
    int f = 0, r = 0;
    int num = 0;
    if (T) {
        p[r++] = T;
        while (f != r) {
            q = p[f++];
            printf("%d", q->num);
            num++;
            if (num < N)
                printf(" ");
            if (q->left)
                p[r++] = q->left;
            if (q->right)
                p[r++] = q->right;
        }
    }
}
struct node *create(int pos[], int pre[], int n) {
    int i = 0, k = 0, root = 0;
    if (n == 0)  return NULL;
    struct node *T;
    T = (struct node *)malloc(sizeof(struct node));
    if (T == NULL)//分配结点内存及判断是否成功
        return NULL;
    root = pos[n - 1];//根节点就是后序遍历的最后一位
    T->num = root;
    for (i = 0; i<n; i++){
        if (pre[i] == root){ //中序遍历
            k = i;
            break;
        }
    }
    T->left = create(pos, pre, k);//递归子树
    T->right = create(pos + k, pre + k + 1, n - k - 1);
    return T;
}

7-23 完全二叉树的层序遍历

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,ans=1;
int a[N],b[N],top=1;
void dfs(int x){
    if(x<=n){
        dfs(x*2);
        dfs(x*2+1);
        b[x]=a[top++];
    }
}
int main()
{
    int i,j;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    dfs(1);
    for(i=1;i<=n;i++){
        if(i!=1) printf(" ");
        printf("%d",b[i]);
    }
    return 0;
    
}

7-24 图深度优先遍历

#include<bits/stdc++.h>
using namespace std;
int book[20005];
vector<int> v[20005];
void dfs(int cur) {
    cout << cur << " ";
    book[cur] = 1;
    int len = v[cur].size();
    for (int i = 0;i < len;i++) {
        if (book[v[cur][i]] == 0) {
            dfs(v[cur][i]);
        }
    }
}
int main() {
    int n, e;
    cin >> n >> e;
    int a, b;
    for (int i = 1;i <= e;i++) {
        cin >> a >> b;
        v[a].push_back(b);
    }
    for (int i = 0;i < n;i++) {
        sort(v[i].begin(), v[i].end());
    }
    for(int i=0;i<n;i++){
        if(book[i]==0)
            dfs(i);
    }

}

7-25 拯救007

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
struct node
{
    int x,y;
}p[110];
int vis[110];
int flag = 0;
int n,m;
int keyi(int x)//如果可以成功到达岸边
{
    if((p[x].x - m<=-50)||(p[x].x + m>=50)||(p[x].y - m<=-50)||(p[x].y + m >=50))
        return 1;
    return 0;
}
int first(int x)//第一步
{
    int p1 = pow(p[x].x,2);
    int p2 = pow(p[x].y,2);
    int r = (m+7.5)*(m+7.5);
    if(p1+p2<=r)
        return 1;
    return 0;
}
int jump(int x,int y)//能否从一个鳄鱼头跳到另一个鳄鱼头
{
    int p1 = pow(p[x].x - p[y].x,2);
    int p2 = pow(p[x].y - p[y].y,2);
    int r = m*m;
    if(p1+p2<=r)
        return 1;
    return 0;
}
int dfs(int t)
{
    vis[t] = 1;
    if(keyi(t) == 1)
    {
        flag = 1;
    }
    for(int i=0;i<n;i++)
    {
        if(!vis[i]&&jump(t,i))
        {
            flag = dfs(i);
//            if(flag == 1)
//                break;
        }
    }
    return flag;
}
int main()
{
    memset(vis,0,sizeof(vis));
    scanf("%d %d",&n,&m);
    int i;
    for(i=0;i<n;i++)
    {
        scanf("%d %d",&p[i].x,&p[i].y);
    }
    if(m>=42.5)
    {
        printf("Yes\n");
    }
    else
    {
        for(i=0;i<n;i++)
        {
            if(!vis[i]&&first(i))
            {
                dfs(i);
            }
        }
        if(flag == 1)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

7-26 拯救007（升级版）

#include<string.h>
#include<stdio.h>
#include<queue>
#include<math.h>
#include<stack>
#include<algorithm>
using namespace std;

#define N 105
#define mem(a) memset(a,-1,sizeof(a))

struct Data{    //保存鳄鱼的每个位置以及每个鳄鱼到岛中心的距离 
 int x,y;
 double dis;
}s[N];
bool cmp(Data a,Data b){
 return a.dis<b.dis;
}

struct Add{  //因为是bfs，所以开一个结构存位置和步数 
 int x;
 int step;
};

bool IsJump(int i,int j); //判断007能否从位置i跳到位置j 
int bfs(int );   //bfs 
bool IsSave(int);  //判断007是否逃离 
double Dis(int i,int j); //计算位置i和位置j的距离 

int vist[N];  //判断当前这个位置的鳄鱼是否访问过，-1表示否，1表示访问过 
int n,m;
int path[N];   //记录路径，初始化为-1 

int main()
{
 scanf("%d %d",&n,&m);
 mem(vist);
 mem(path);
 for(int i=0;i<n;i++){
  scanf("%d %d",&s[i].x,&s[i].y);
  s[i].dis=fabs(sqrt(pow(s[i].x,2)+pow(s[i].y,2)));  //因为如果路径不唯一，
  //挑离第一跳最近的点，所以把所有鳄鱼距离岛中心的距离算出来取绝对值，
  //然后递增排序 
 }
 sort(s,s+n,cmp);
 int flag=0;
 if(m+7.5>=50){  //如果最大距离加上岛的半径大于等于边界就可以直接出去 
  flag=1;  //这样算一步，没有路径。 
  printf("1\n");
 } 
 else{
  for(int i=0;i<n;i++){
   if(vist[i]==-1&&m+7.5>=sqrt(pow(s[i].x,2)+pow(s[i].y,2))&&s[i].dis>7.5){ //首先判断当前位置是否已经访问
   //并且第一跳是否满足条件，还有如果鳄鱼距离岛中心的位置小于等于岛的半径
   //那肯定不会选择，因为题目要求的是最短路径 
    flag=bfs(i);
    if(flag){  //flag为真就说明已经逃生，循环直接退出 
     break;
    }
   }
  } 
 }
 if(!flag){
  printf("0\n");
 }
 return 0;
}

double Dis(int i,int j){
 return sqrt(pow((s[j].x-s[i].x),2)+pow((s[j].y-s[i].y),2));
}

bool IsSave(int i){
 if(s[i].x+m>=50||s[i].x-m<=-50||s[i].y+m>=50||s[i].y-m<=-50){
  return true;
 }
 else{
  return false;
 }
} 

bool IsJump(int i,int j){
 if(Dis(i,j)<=m)
  return true;
 else
  return false;
}

int bfs(int i){
 struct Add p,temp;
 queue<Add>q;
 p.x=i;
 p.step=1;
  q.push(p);
 while(!q.empty()){
   temp=q.front();
  if(IsSave(temp.x)){  //判断当面的距离加上可以跳的最大距离能否逃离 
   printf("%d\n",temp.step+1);
   stack<int>S;
   while(temp.x!=-1){  //因为输出的路径要求是从第一跳的位置到最后一跳的路径 
   //但是存的是最后一跳到第一跳的路径，所以把路径先压入栈，然后再输出就对了 
    S.push(temp.x);
    temp.x=path[temp.x];
   }
   while(!S.empty()){
    printf("%d %d\n",s[S.top()].x,s[S.top()].y);
    S.pop();
   }
   return 1;
  }
  q.pop();
  vist[temp.x]=1;
  for(int j=0;j<n;j++){
   if(vist[j]==-1&&IsJump(temp.x,j)&&s[j].dis>7.5){//寻找未访问过，且满足下一跳的鳄鱼坐标 
    //并且在小岛外的鳄鱼 
    vist[j]=1;  //标记访问  
    p.x=j;
    p.step=temp.step+1; //当前步数是上一步加1 
    path[j]=temp.x;  //存储路径 
    q.push(p); //压入队列 
   }
  }
 }
 return 0;  
}

7-27 深入虎穴

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
//节点 
struct node{
    int num;//节点的编号
    int pre;//前驱节点编号
    vector<int> next;//后继节点集合 
};

int main()
{
    int k;scanf("%d",&k);
    node nodes[k+1];//K个节点 
    int roots[k+1]={0};//这个数组用来找到根节点 
    int root;//根节点 
    for (int i=1;i<=k;i++){
        int t;scanf("%d",&t);
        nodes[i].num=i;
        for (int j=0;j<t;j++){
            int tt;scanf("%d",&tt);
            nodes[i].next.push_back(tt);
            nodes[tt].pre=i;//找到节点的前驱节点 
            roots[tt]++;//tt这个节点有入度 记录下来 
        }
    }
    //找到根节点
    for (int i=1;i<=k;i++) {
        if (roots[i]==0)root=i;//因为根节点入度为0 
    }
    int path[k+1]={0};//path[i]代表第i个节点到root的长度 
    path[root]=0;
    //树的层次遍历 老套路题啦~ 
    queue<int>q;
    q.push(root);
    while(!q.empty()){
        int t=q.front();
        q.pop();
        if (t!=root)path[t]=path[nodes[t].pre]+1;
        for (int i=0;i<nodes[t].next.size();i++){
            q.push(nodes[t].next[i]);
        }
    }
    int v=0,index=root;
    //找到离root最远的那道门 
    for (int i=1;i<=k;i++){
        if (path[i]>v){
            v=path[i];index=i;
        }
    }
    cout<<index;
}