Can I Post the letter - 程序设计

题目描述
I am a traveler. I want to post a letter to Merlin. But because there are so many roads I can walk through, and maybe I can’t go to Merlin’s house following these roads, I must judge whether I can post the letter to Merlin before starting my travel. Suppose the cities are numbered from 0 to N-1, I am at city 0, and Merlin is at city N-1. And there are M roads I can walk through, each of which connects two cities. Please note that each road is direct, i.e. a road from A to B does not indicate a road from B to A. Please help me to find out whether I could go to Merlin’s house or not.
机器翻译：

我是一个旅行者.我想给梅林写一封信。但是因为可以走过的道路太多了，也许我不能沿着这些路去梅林家，所以我必须在开始旅行之前判断我是否可以把信寄给梅林。假设城市编号从 0 到 N-1，我在城市 0，而梅林在城市 N-1。有M条路我可以走过，每条路都连接两个城市。请注意，每条道路都是直达的，即从A到B的道路并不表示从B到A的道路。请帮我看看我是否可以去梅林的家。

输入描述
There are multiple input cases. For one case, first are two lines of two integers N and M, (N<=200, M<=N*N/2), that means the number of citys and the number of roads. And Merlin stands at city N-1. After that, there are M lines. Each line contains two integers i and j, what means that there is a road from city i to city j.
The input is terminated by N=0.

机器翻译：

有多种输入情况。对于一种情况，首先是两条由两个整数 N 和 M 组成的线，（N<=200，M<=N*N/2），表示城市数量和道路数量。梅林站在N-1号城市。之后，有M线。每行包含两个整数 i 和 j，这意味着有一条从城市 i 到城市j 的道路。输入以 N=0 终止。

输出描述
For each test case, if I can post the letter print “I can post the letter” in one line, otherwise print “I can't post the letter”.

输入样例

输出样例

I can post the letter
I can't post the letter

Yizuodi的答案

#include <iostream>
#include <cstring>
using namespace std;
int E[200][200];//使用矩阵表示图
int visited[200];//1已被访问 0未被访问
int N,M;//城市数量和道路数量

void DFS(int a)//进行深度优先搜索
{
    visited[a] = 1;//节点a已被访问
    for (int i=0;i<N;i++)
    {
        if (!visited[i]&&E[a][i] == 1)
        {
            DFS(i);
        }
    }
}

int main()
{
    while (cin>>N && N)//输入城市数量
    {
        cin>>M;//输入道路数量
        memset(visited,0,sizeof(visited));//将visited数组全部置0
        memset(E,0,sizeof(E));//将矩阵置0
        for (int i=0;i<M;i++)//输入M条边的信息
        {
            int a,b;
            cin>>a>>b;
            E[a][b] = 1;//为有向图
        }
        DFS(0);//进行深度优先搜索
        if (visited[N-1])//看第N-1个节点是否被访问过
        {
            cout<<"I can post the letter"<<endl;
        }
        else
        {
            cout<<"I can't post the letter"<<endl;
        }
    }
}

答案

#include <iostream>
using namespace std;

void DFS(const int i,int &N,int (&E)[200][200],int (&visited)[200])
{
    visited[i] = 1;
    for (int j=0;j<N;j++)
    {
        if (E[i][j] == 1)
        {
            if (!visited[j])
                DFS(j,N,E,visited);
        }
    }
}

int main()
{
    int N = 0,M = 0;
    while (cin>>N && N)
    {
        int E[200][200] = {0};
        int i,j;    
        cin>>M;
        for (int t=0;t<M;t++)
        {
            cin>>i>>j;
            E[i][j] = 1;
        }
        
        int visited[200] = {0};
        DFS(0,N,E,visited);
        
        if (visited[N-1])
            cout<<"I can post the letter"<<endl;
        else
            cout<<"I can't post the letter"<<endl;
    }
    
    return 0;
}