pat 1032 sharing

Attention

注意:相同节点不只是节点对应的字符相等,地址 , next也要相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <cstdio>
#define MAX 100010
/*
注意:相同节点不只是节点对应的字符相等,地址 , next也要相等
*/
typedef struct
{
char ch;
int next;
}Lnode;
int main()
{
int start1 , start2 , N , res = -1;
//cin>>start1>>start2>>N;
scanf("%d%d%d" , &start1 , &start2 , &N);
int i ;
Lnode List[MAX];
for(i = 0 ; i < N ; ++i)
{
int ad , next;
char ch;
//cin>>ad>>ch>>next;
scanf("%d %c %d" , &ad , &ch , &next);
List[ad].ch = ch;
List[ad].next = next;
}
//deal
int len1 = 1 , len2 = 1;
int temp = start1;
do
{
++len1;
temp = List[temp].next;
}while(List[temp].next != -1);
temp = start2;
do
{
++len2;
temp = List[temp].next;
}while(List[temp].next != -1);
int longStart , shortStart , dist;
if(len1 - len2 > 0)
{
dist = len1 - len2;
longStart = start1;
shortStart = start2;
}
else
{
dist = len2 - len1;
longStart = start2;
shortStart = start1;
}
// temp = longStart;
while(dist)
{
longStart = List[longStart].next;
dist--;
}
bool flag = true , isContinue = false;
while(true)
{
while(List[longStart].ch == List[shortStart].ch && longStart == shortStart)
{
if(flag)
{
res = longStart;
flag = false;
}
longStart = List[longStart].next;
shortStart = List[shortStart].next;
isContinue = false;
if(List[longStart].next == -1 && List[longStart].ch == List[shortStart].ch)
break;
}
if(List[longStart].next == -1 && List[longStart].ch == List[shortStart].ch)
break;
else if(List[longStart].next == -1 && List[longStart].ch != List[shortStart].ch)
{
isContinue = true;
break;
}
longStart = List[longStart].next;
shortStart = List[shortStart].next;
}
if(isContinue)
res = -1;
if(res >= 0)//Attention!!!
printf("%05d\n" , res);
else
printf("-1\n");
return 0;
}

热评文章