[廣度優先搜索]NOIP模擬題：傳話 message 解題報告

[問題描述]

興趣小組的同學來自各個學校，爲了增加友誼，晚會上又進行了一個傳話遊戲，如果 a 認識 b ，那麼 a 收到某個消息，就會把這個消息傳給 b ，以及所有 a 認識的人。

如果 a 認識 b ， b 不一定認識 a 。

所有人從 1 到 n 編號，給出所有“認識”關係，問如果 i 發佈一條新消息，那麼會不會經過若干次傳話後，這個消息傳回給了 i ， 1<=i<=n 。

[輸入文件]

輸入文件 message.in 中的第一行是兩個數 n(n<1000) 和 m(m<10000) ，兩數之間有一個空格，表示人數和認識關係數。

接下來的 m 行，每行兩個數 a 和 b ，表示 a 認識 b 。 1<=a, b<=n 。認識關係可能會重複給出，但一行的兩個數不會相同。

[輸出文件]

輸出文件 message.out 中一共有 n 行，每行一個字符 T 或 F 。第 i 行如果是 T ，表示 i 發出一條新消息會傳回給 i ；如果是 F ，表示 i 發出一條新消息不會傳回給 i 。

[輸入樣例]

4 6

1 2

2 3

4 1

3 1

1 3

2 3

[輸出樣例]

T

T

T

F

【解題報告】

直接廣度優先搜索即可。

深度優先搜索只能過4組數據。

每一次bfs時間複雜度為O(n)，所以n次總時間複雜度O(n^2) 。

【我的代碼】

#include <cstdlib>
#include <cstdio>
#include <iostream>
using namespace std;
int N;
int M;
int Mat[1001][1001];
int Abut[1001]={0};

void init()
{
    scanf("%d %d\n",&N,&M);
   
    int a,b;
    for (int i=1;i<=M;i++)
    {
        scanf("%d %d\n",&a,&b);
        Mat[a][++Abut[a]]=b;
    }
}


bool bfs(int S)
{
    int big=1;
    int sma=0;
    int Q[1001]={0};
    bool used[2001]={false};
    Q[0]=S;
    while(sma<=big)
    {
        if(Q[sma]==S && sma!=0)
            return true;
        for (int i=1;i<=Abut[Q[sma]];i++)
        {
            if(used[Mat[Q[sma]][i]])
                continue;
            Q[big++]=Mat[Q[sma]][i];
            used[Mat[Q[sma]][i]]=true;
        }
        sma++;
    }
    return false;
}

int main()
{
    freopen("messagez.in","r",stdin);
    freopen("messagez.out","w",stdout);
    init();
    for (int i=1;i<=N;i++)
    {
        if(bfs(i))
            cout<<"T"<<endl;
        else
            cout<<"F"<<endl;
    }
    return 0;
}