[数据结构与算法]7-2 Rank a Linked List (25 分) （链表 读清题意 5/20

添加链接描述
找到第一个起点 也就是没有入度的点 然后遍历即可 要看清题意
注意题目求的是遍历的顺序，而不是编号
第一个程序是从尾到头 第二个是结束了写的从头到尾
Now let’s number these nodes in order, starting from the first node, by numbers from 1 to n. These numbers are called the ranks of the nodes. Your job is to list their ranks.

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+9;
map<int,int>mp;
int vis[N];
int main(){
    int n;
    cin>>n;int root=-1;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        mp[x]=i;
        if(x==-1)root=x;
        
    }
    int arr[N]={},tot=1;
    while(tot<=n){
        arr[mp[root]]=tot++;
        root=mp[root];
    }
    // cout<<st.top()+1;
    // st.pop();
   int ok=0;
    for(int i=0;i<n;i++){
        if(ok)cout<<" ";
        cout<<tot-arr[i];
        
        ok=1;
    }



    // for(int i=0;i<n;i++){
    //     if(vis[i]==0){root=i;break;}
    // }
    // cout<<root+1;
    // int p=0;
    // for(int i=2;;i++){
    //     p=t[root].ne;
    //     if(p==-1)break;
    //     cout<<" "<<p+1;
    //     root=p;

    // }
    // cout<<endl;
    return 0;
}
/*
8
3 0 1 5 2 -1 4 6
8 7 5 3 2 1 4 6
*/

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+9;
struct node {
    int data;
    int ne;
}t[N];
int arr[N];
int vis[N];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        t[i].ne=x;
        vis[x]++;
    }
    int root=-1;
    for(int i=0;i<n;i++){
        if(vis[i]==0)root=i;
    }
    arr[root]=1;
    for(int i=2;i<=n;i++){
        int p=t[root].ne;
        // cout<<" "<<p+1;
        arr[p]=i;
        root=p;
    }
    cout<<arr[0];
    for(int i=1;i<n;i++)cout<<" "<<arr[i];
    return 0;
}
/*
8
3 0 1 5 2 -1 4 6
*/