13 struct conn
*connections
;
17 struct node
*get_or_create(struct node
**graph
, char name
[])
20 HASH_FIND_STR(*graph
, name
, n
);
24 n
= malloc(sizeof(struct node
));
26 n
->connections
= NULL
;
27 HASH_ADD_STR(*graph
, key
, n
);
32 void add_connection(struct node
*from
, struct node
*to
)
35 struct conn
*c
= malloc(sizeof(struct conn
));
36 strcpy(c
->key
, to
->key
);
38 HASH_ADD_STR(from
->connections
, key
, c
);
40 c
= malloc(sizeof(struct conn
));
41 strcpy(c
->key
, from
->key
);
43 HASH_ADD_STR(to
->connections
, key
, c
);
46 char **copy_visited(char **visited
, int nvisited
)
48 char **r
= malloc(sizeof(char *)*nvisited
);
49 memcpy(r
, visited
, sizeof(char *)*nvisited
);
53 int find_end(struct node
*node
, char **visited
, int nvisited
)
55 if (strcmp(node
->key
, "end") == 0)
57 if (islower(node
->key
[0])) {
58 for (int i
= 0; i
<nvisited
; i
++)
59 if (strcmp(node
->key
, visited
[i
]) == 0)
61 visited
= realloc(visited
, sizeof(char *)*(nvisited
+1));
62 visited
[nvisited
++] = node
->key
;
65 for (struct conn
*c
= node
->connections
; c
!= NULL
; c
= c
->hh
.next
)
66 r
+= find_end(c
->node
, copy_visited(visited
, nvisited
), nvisited
);
73 struct node
*graph
= NULL
;
76 while (getline(&buf
, &len
, stdin
) != -1) {
77 char *toname
= strchr(buf
, '-');
79 if (toname
[strlen(toname
)-1] == '\n')
80 toname
[strlen(toname
)-1] = '\0';
81 add_connection(get_or_create(&graph
, buf
),
82 get_or_create(&graph
, toname
));
85 printf("%d\n", find_end(get_or_create(&graph
, "start"), NULL
, 0));