|
|
用鄰接表存邊，需要記錄路徑。
 #include <stdio.h>
#define MAX_N 50032
#define MAX_K 1024
  struct queue_node  {
 int step, idx;
struct queue_node *prev;
 };
struct queue_node queue[MAX_K];
struct edge_node {
int idx;
struct edge_node *next;
};
struct edge_node edges[MAX_N], *map[MAX_K];
int qh, qt, N, K, visited[MAX_K], path[MAX_K];
__inline int push(int idx, int step, struct queue_node *prev)
{
if (visited[idx])
return 0;
visited[idx]++;
queue[qt].idx = idx;
queue[qt].step = step;
queue[qt].prev = prev;
qt++;
return idx == K;
}
int main()
{
int i, a, b;
struct queue_node *t;
struct edge_node *e;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &N, &K);
  for (i = 0; i < N; i++) {
scanf("%d%d", &a, &b);
edges[i].idx = b;
edges[i].next = map[a];
map[a] = &edges[i];
 }
push(1, 1, NULL);
while (qh != qt) {
t = &queue[qh++];
for (e = map[t->idx]; e; e = e->next)
if (push(e->idx, t->step + 1, t))
break;
if (e)
break;
}
if (qh == qt) {
printf("-1\n");
return 0;
}
t = &queue[--qt];
printf("%d\n", t->step);
for (i = 0; t; t = t->prev)
path[i++] = t->idx;
for (i--; i >= 0; i--)
printf("%d\n", path[i]);
return 0;
}
|