50189. Find a Path
難度：4.4/5
本來是\(O(n)\)查找有沒有出去過一個點（開一個array紀錄點的index），後來才想到可以直接把visited記錄在map上，就可以\(O(1)\)查找。
Second Try: 4/5 Used Time: 24:021
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#include <stdio.h>
#include <stdlib.h>
typedef struct{
int a;
int b;
} p;
typedef struct{
int idx;
int ptr;
} s_map;
int cmp(const void* aa, const void* bb){
p* a = (p*)aa;
p* b = (p*)bb;
if(a->a != b->a) return (a->a > b->a) ? 1 : -1;
else return (a->b > b->b) ? 1 : -1;
}
int m;
int q;
p g[20000];
s_map map[20000];
int map_cnt = 0;
int binary_search(int num){
int l = 0, r = map_cnt - 1;
while(l <= r){
int m = (l + r) / 2;
if(map[m].idx == num) return m;
else if(map[m].idx > num) r = m - 1;
else l = m + 1;
}
return -1;
}
int is_in(int arr[], int arr_size, int t){
for(int i = 0; i < arr_size; i++){
if(arr[i] == t) return 1;
}
return 0;
}
int check(int a, int b, int vis[]){
if(a == b) return 1;
int idx = binary_search(a); if(idx == -1) return 0;
if(vis[idx] == 1) return 0;
else vis[idx] = 1;
int ptr = map[idx].ptr;
for(int i = ptr; g[i].a == a; i++){
int rtv = check(g[i].b, b, vis);
if(rtv == 1) return 1;
}
return 0;
}
int main(){
scanf("%d", &m);
for(int i = 0; i < m; i++){
int a, b; scanf("%d %d", &a, &b);
g[i].a = a, g[i].b = b;
g[i + m].a = b, g[i + m].b = a;
}
qsort(g, 2 * m, sizeof(p), cmp);
for(int i = 0; i < 2 * m; i++){
if(i == 0 || g[i].a != g[i - 1].a){
map[map_cnt].idx = g[i].a;
map[map_cnt].ptr = i;
map_cnt++;
}
}
scanf("%d", &q);
while(q--){
int a, b; scanf("%d %d", &a, &b);
int vis[10000] = {0};
if(check(a, b, vis)) printf("There is a path.\n");
else printf("There is no path.\n");
}
}