//1032 Sharing 天勤 算法下P270算法上262（链表）静态链表

//1032 Sharing 天勤 算法下P270   算法上262
#include <iostream>
#define maxSize 100000
using namespace std;

struct Node{
    char data;
    int next;
    int flag;
};

int main(){
    int Ad1,Ad2,N;
    Node node[maxSize];
    cin>>Ad1>>Ad2>>N;
    int ad,next;
    char data;

    for(int i=0;i<N;i++){
        cin>>ad>>data>>next;
        node[ad].data = data;
        node[ad].next = next;
        node[ad].flag = 0;


    }

    int p = Ad1;
    while(p != -1){
        node[p].flag = 1;
        p = node[p].next;
    }


    int q = -1;
    p = Ad2;
    while(p != -1){
        if(node[p].flag == 1){
            q = p;
            break;
        }
        p = node[p].next;
    }

    if(q != -1)  printf("%05d",q);
    else printf("-1");

    return 0;
}
//算法笔记上P262
#include <cstdio>
#include <cstring>
const int maxn = 100010;

struct NODE{
    char data;
    int next;
    bool flag;
}node[maxn];

int main(){
    for(int i=0;i<maxn;i++){
        node[i].flag = false;
    }
    int s1,s2,n;
    scanf("%d%d%d",&s1,&s2,&n);
    int address,next;
    char data;
    for(int i=0;i<n;i++){
        scanf("%d %c %d",&address,&data,&next);
        node[address].data = data;
        node[address].next = next;
    }

    int p;
    for(p=s1;p != -1;p = node[p].next){
        node[p].flag = true;
    }
    for(p=s2;p!=-1;p=node[p].next){
        if(node[p].flag) break;
    }
    if(p != -1){
        printf("%05d\n",p);
    }else{
        printf("-1\n");
    }

    return 0;

}






算法笔记上P265

PAT A1052

//算法笔记上P266
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100010;

struct Node{

    int address,next,data;
    bool flag;
}node[maxn];

bool cmp(Node a,Node b){
    if(a.flag == false || b.flag == false){
        return a.flag > b.flag; //???? 只要a和b中有一个无效节点，就把他放后面去
    }else{
        return a.data < b.data;
    }
}



int main(){
    for(int i=0;i<maxn;i++){
        node[i].flag = false;
    }
    int n,begin,address;
    scanf("%d%d",&n,&begin);
    for(int i=0;i<n;++i){
        scanf("%d",&address);
        scanf("%d%d",&node[address].data,&node[address].next);
        node[address].address = address;
    }
    int count = 0,p = begin;

    while(p != -1){
        node[p].flag = true;
        count++;
        p = node[p].next;
    }

    if(count == 0){
        printf("0 -1");
    }else{
        sort(node,node+maxn,cmp);

        printf("%d %05d\n",count,node[0].address);
        for(int i=0;i<count;i++){
            if(i != count -1){
                printf("%05d %d %05d\n",node[i].address,node[i].data,node[i+1].address);
            }else{
                printf("%05d %d -1\n",node[i].address,node[i].data);
            }
        }
    }


    return 0;

}