think: 1題目注意超時，自己剛開始用的深度優先搜索和有序鄰接表，超時 推測如果用鄰接矩陣可能會直接runtime error 2反思:根據題意選用適合的數據結構，這個題目建議用廣度優先搜索和鄰接表
圖結構練習——BFSDFS——判斷可達性 Time Limit: 1000MS Memory Limit: 65536KB
PRoblem Description 在古老的魔獸傳說中，有兩個軍團，一個叫天災，一個叫近衛。在他們所在的地域，有n個隘口，編號為1..n，某些隘口之間是有通道連接的。其中近衛軍團在1號隘口，天災軍團在n號隘口。某一天，天災軍團的領袖巫妖王決定派兵攻打近衛軍團，天災軍團的部隊如此龐大，甚至可以填江過河。但是巫妖王不想付出不必要的代價，他想知道在不修建任何通道的前提下，部隊是否可以通過隘口及其相關通道到達近衛軍團展開攻擊。由于n的值比較大（n<=1000），于是巫妖王找到了擅長編程的你 =_=，請你幫他解決這個問題，否則就把你吃掉變成他的魔法。為了拯救自己，趕緊想辦法吧。
Input 輸入包含多組，每組格式如下。 第一行包含兩個整數n,m（分別代表n個隘口，這些隘口之間有m個通道）。 下面m行每行包含兩個整數a，b；表示從a出發有一條通道到達b隘口（注意：通道是單向的）。
Output 如果天災軍團可以不修建任何通道就到達1號隘口，那么輸出YES，否則輸出NO。
Example Input 2 1 1 2 2 1 2 1
Example Output NO YES
Hint Author 趙利強
以下為accepted代碼——廣度優先搜索+無序鄰接表
#include <stdio.h>#include <string.h>#include <stdlib.h>struct node{ int Data; struct node *next;}*a[1004], *p;int visit[1004], link[1004];int tp, op, flag;void BFS(int n){ op++; p = a[n]; while(p != NULL) { if(p->Data == 1) { flag = 1; return; } if(visit[p->Data] == 0) { link[tp++] = p->Data; visit[p->Data] = 1; } p = p->next; } if(op <= tp) BFS(link[op]);}int main(){ int n, m, i, u, v; while(scanf("%d %d", &n, &m) != EOF) { flag = 0; tp = op = 0; memset(visit, 0, sizeof(visit)); for(i = 0; i <= n; i++) a[i] = NULL; while(m--) { scanf("%d %d", &u, &v); if(a[u] == NULL) { p = (struct node *)malloc(sizeof(struct node)); p->Data = v; p->next = NULL; a[u] = p; } else { p = (struct node *)malloc(sizeof(struct node)); p->Data = v; p->next = a[u]->next; a[u]->next = p; } } //DFS(n); link[tp++] = n; visit[n] = 1; BFS(n); if(flag) printf("YES/n"); else printf("NO/n"); } return 0;}/***************************************************User name: Result: AcceptedTake time: 60msTake Memory: 4484KBSubmit time: 2017-02-15 20:23:35****************************************************/以下為time limit exceeded代碼——深度優先搜索+有序鄰接表
#include <stdio.h>#include <string.h>#include <stdlib.h>struct node{ int Data; struct node *next;}*a[1004], *p, *q;int visit[1004], link[1004];int tp, op, flag;void DFS(int n){ if(n == 1) { flag = 1; return; } if(a[n] == NULL) return; p = a[n]->next; while(p != NULL) { if(visit[p->Data] == 0) { visit[p->Data] = 1; DFS(p->Data); } p = p->next; }}void BFS(int n){ if(n == 1) { flag = 1; return; } op++; p = a[n]; while(p != NULL) { if(visit[p->Data] == 0) { link[tp++] = p->Data; visit[p->Data] = 1; } p = p->next; } if(op <= tp) BFS(link[op]);}int main(){ int n, m, i, u, v; while(scanf("%d %d", &n, &m) != EOF) { flag = 0; tp = op = 0; memset(visit, 0, sizeof(visit)); for(i = 0; i <= n; i++) a[i] = NULL; while(m--) { scanf("%d %d", &u, &v); if(a[u] == NULL) { p = (struct node *)malloc(sizeof(struct node)); p->Data = u; p->next = NULL; a[u] = p; p = (struct node *)malloc(sizeof(struct node)); p->Data = v; p->next = NULL; a[u]->next = p; } else { p = (struct node *)malloc(sizeof(struct node)); p->Data = v; p->next = NULL; q = a[u]->next; if(q == NULL) { p->next = a[u]->next; a[u]->next = p; } while(q != NULL) { if(q->next == NULL) { if(p->Data >= q->Data) { p->next = q->next; q->next = p; } } else if(q->next != NULL) { if(p->Data >= q->Data && p->Data < q->next->Data) { p->next = q->next; q->next = p; } } q = q->next; } } } //DFS(n); link[tp++] = n; visit[n] = 1; BFS(n); if(flag) printf("YES/n"); else printf("NO/n"); } return 0;}/***************************************************User name: Result: Time Limit ExceededTake time: 1010msTake Memory: 0KBSubmit time: 2017-02-15 20:12:04****************************************************/新聞熱點
疑難解答
