2138=数据结构实验之图论三:判断可达性

waitwolf 2019-11-09

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INF 0x3f3f3f3f
int map[1000][1000],visited[1000];
int n,m;
int flag;
void DFS(int t)
{
    int i;
    visited[t]=1;
    for(i=n; i>=1; i--)
    {
        if(visited[i]==0&&map[t][i]==1)
        {
            DFS(i);
        }
    }
}
int main()
{
    while(~scanf("%d %d",&n,&m))
    {
        int i;
        memset(map,0,sizeof(map));
        memset(visited,0,sizeof(visited));
        for(i=1; i<=m; i++)
        {
            int a,b;
            scanf("%d %d",&a,&b);
            map[a][b]=1;
        }
        DFS(n);
        if(visited[1]==1)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

相关推荐