題目描述

在古老的魔獸傳說中，有兩個(gè)軍團(tuán)，一個(gè)叫天災(zāi)，一個(gè)叫近衛(wèi)。在他們所在的地域，有n個(gè)隘口，編號(hào)為1..n，某些隘口之間是有通道連接的。其中近衛(wèi)軍團(tuán)在1號(hào)隘口，天災(zāi)軍團(tuán)在n號(hào)隘口。某一天，天災(zāi)軍團(tuán)的領(lǐng)袖巫妖王決定派兵攻打近衛(wèi)軍團(tuán)，天災(zāi)軍團(tuán)的部隊(duì)如此龐大，甚至可以填江過河。但是巫妖王不想付出不必要的代價(jià)，他想知道在不修建任何通道的前提下，部隊(duì)是否可以通過隘口及其相關(guān)通道到達(dá)近衛(wèi)軍團(tuán)展開攻擊。由于n的值比較大（n<=1000），于是巫妖王找到了擅長編程的你 =_=，請(qǐng)你幫他解決這個(gè)問題，否則就把你吃掉變成他的魔法。為了拯救自己，趕緊想辦法吧。

輸入

輸入包含多組，每組格式如下。 第一行包含兩個(gè)整數(shù)n,m（分別代表n個(gè)隘口，這些隘口之間有m個(gè)通道）。 下面m行每行包含兩個(gè)整數(shù)a，b；表示從a出發(fā)有一條通道到達(dá)b隘口（注意：通道是單向的）。

輸出

如果天災(zāi)軍團(tuán)可以不修建任何通道就到達(dá)1號(hào)隘口，那么輸出YES，否則輸出NO。

示例輸入

2 1 1 2 2 1 2 1

示例輸出

NO YES

提示

[cpp]?view plaincopyprint?

#include?<stdio.h>??

#include?<string.h>??

int?map1[1001][1001];??

int?visit[10000];??

int?dfs(int?i,?int?n)??

{??

????int?j,?x=0;??

????visit[i]=1;??

????for(j=1;?j<=n;?j++)??

????{??

????????if(!visit[j]&&map1[i][j])??

????????{??

????????????if(j==1)??

????????????????return?1;??

????????????else??

????????????????x=dfs(j,n);??

????????????if(x)??

????????????????break;??

????????}??

????}??

????if(j>n)?return?0;??

????else??

????{??

????????if(x)??

????????????return?1;??

????????else??

????????????return?0;??

????}??

}??

??

int?main()??

{??

????int?n,?m,?i,?j,?x,?a,?b;??

????while(scanf("%d%d",&n,&m)!=EOF)??

????{??

????????x=0;??

????????memset(map1,0,sizeof(map1));??

????????memset(visit,0,sizeof(visit));??

????????for(i=0;?i<m;?i++)??

????????{??

????????????scanf("%d%d",&a,&b);??

????????????map1[a][b]=1;??

????????}??

????????x=dfs(n,n);??

????????if(x)??

????????????printf("YES\n");??

????????else??

????????????printf("NO\n");??

????}??

????return?0;??

}??

總結(jié)

以上是生活随笔為你收集整理的图结构练习——DFS——判断可达性的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。