B1032 Sharing (链表相交)

B1032 Sharing (25分)

• 结构体

struct node
{
      int address;
      char c;
      int next; 
      int flag;//标记完全相同的结点
}

• 注意点

1.scanf()使用%c格式输入时是可以读入空格的，因此在输入地址，数据及后继结点地址时，格式不能写成%d%c%d，必须在中间加空格%d %c %d

2.若使用map，最后一组数据会超时

3.此处相交的结点要求是完全相同的结点，即data相同但address不同的结点不是相交的结点

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

const int MAX=1e6+10;

struct node
{
    int address;
    char data;
    int next;
    int flag;
}Node[MAX];

map<char,int>book;

int main()
{
    int st1,st2,n;
    for(int i=0;i<MAX;i++)
    {
        Node[i].flag=0;
    }
    scanf("%d%d%d",&st1,&st2,&n);
    for(int i=0;i<n;i++)
    {
        int address;
        scanf("%d",&address);
        scanf(" %c %d",&Node[address].data,&Node[address].next);
        Node[address].address=address;
    }
    int p=st1;
    while(p!=-1)
    {
        Node[p].flag=1;
        p=Node[p].next;
    }
    p=st2;
    while(p!=-1)
    {
        if(Node[p].flag==1)
            break;
        p=Node[p].next;
    }
    if(p!=-1)
        printf("%05d\n",Node[p].address);
    else
        printf("-1\n");
    return 0;
}