14 struct conn
*connections
;
18 struct node
*get_or_create(struct node
**graph
, char name
[])
21 HASH_FIND_STR(*graph
, name
, n
);
25 n
= malloc(sizeof(struct node
));
27 n
->connections
= NULL
;
28 HASH_ADD_STR(*graph
, key
, n
);
33 void add_connection(struct node
*from
, struct node
*to
)
36 struct conn
*c
= malloc(sizeof(struct conn
));
37 strcpy(c
->key
, to
->key
);
39 HASH_ADD_STR(from
->connections
, key
, c
);
41 c
= malloc(sizeof(struct conn
));
42 strcpy(c
->key
, from
->key
);
44 HASH_ADD_STR(to
->connections
, key
, c
);
47 char **copy_visited(char **visited
, int nvisited
)
49 char **r
= malloc(sizeof(char *)*nvisited
);
50 memcpy(r
, visited
, sizeof(char *)*nvisited
);
54 int find_end(struct node
*node
, char **visited
, int nvisited
, bool twice
, char **path
, int npath
)
56 if (strcmp(node
->key
, "end") == 0) {
58 for (int i
= 0; i
<npath
; i
++)
59 printf("%s,", path
[i
]);
63 if (islower(node
->key
[0])) {
64 for (int i
= 0; i
<nvisited
; i
++)
65 if (strcmp(node
->key
, visited
[i
]) == 0)
67 visited
= realloc(visited
, sizeof(char *)*(nvisited
+1));
68 visited
[nvisited
++] = node
->key
;
70 path
= realloc(path
, sizeof(char *)*(npath
+1));
71 path
[npath
++] = node
->key
;
73 for (struct conn
*c
= node
->connections
; c
!= NULL
; c
= c
->hh
.next
) {
74 if (twice
&& strcmp(node
->key
, "start") != 0 && islower(node
->key
[0]))
75 r
+= find_end(c
->node
, copy_visited(visited
, nvisited
-1), nvisited
-1, false, copy_visited(path
, npath
), npath
);
76 r
+= find_end(c
->node
, copy_visited(visited
, nvisited
), nvisited
, twice
, copy_visited(path
, npath
), npath
);
84 struct node
*graph
= NULL
;
87 while (getline(&buf
, &len
, stdin
) != -1) {
88 char *toname
= strchr(buf
, '-');
90 if (toname
[strlen(toname
)-1] == '\n')
91 toname
[strlen(toname
)-1] = '\0';
92 add_connection(get_or_create(&graph
, buf
),
93 get_or_create(&graph
, toname
));
96 find_end(get_or_create(&graph
, "start"), NULL
, 0, true, NULL
, 0);
97 // printf("%d\n", find_end(get_or_create(&graph, "start"), NULL, 0, true, NULL, 0));