http://codevs.cn/problem/1506/

1506 传话

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 白银 Silver

题解

题目描述 Description

一个朋友网络，如果a认识b，那么如果a第一次收到某个消息，那么会把这个消息传给b，以及所有a认识的人。

如果a认识b，b不一定认识a。

所有人从1到n编号，给出所有“认识”关系，问如果i发布一条新消息，那么会不会经过若干次传话后，这个消息传回给了i，1<=i<=n。

输入描述 Input Description

第一行是n和m，表示人数和认识关系数。

接下来的m行，每行两个数a和b，表示a认识b。1<=a, b<=n。认识关系可能会重复给出，但一行的两个数不会相同。

输出描述 Output Description

一共n行，每行一个字符T或F。第i行如果是T，表示i发出一条新消息会传回给i；如果是F，表示i发出一条新消息不会传回给i。

样例输入 Sample Input

4 6

1 2

2 3

4 1

3 1

1 3

2 3

样例输出 Sample Output

数据范围及提示 Data Size & Hint

n<=1000

1<=a, b<=n

分析：

广搜，因为如果搜索到某层K,如果不是由i层转回到i层的一条回路，而是一条死路，那么以后必然也不用搜索这层了。

AC代码：

 #include <stdio.h>

 #include <algorithm>

 #include <iostream>

 #include <string.h>

 #include <string>

 #include <math.h>

 #include <stdlib.h>

 #include <queue>

 #include <stack>

 #include <set>

 #include <map>

 #include <list>

 #include <iomanip>

 #include <vector>

 #pragma comment(linker, "/STACK:1024000000,1024000000")

 #pragma warning(disable:4786)

 using namespace std;

 const int INF = 0x3f3f3f3f;

 const int MAX = 1e3 + ;

 const double eps = 1e-;

 const double PI = acos(-1.0);

 bool f[MAX][MAX];

 bool mark[MAX];

 int n,m,a,b,flag,i;

 void bfs(int start)

 {

     queue<int >q;

     int p;

     q.push(start);

     while(!q.empty())

     {

         int temp=q.front();  q.pop();

         for(p=;p<=n;p++)

         {

             if(f[temp][p]&&!mark[p])

             {

                 mark[p]=;

                 q.push(p);

             }

             if(mark[i])

             {

                 flag=;

                 return ;

             }

         }

     }

 }

 int main()

 {

     cin>>n>>m;

     memset(f,,sizeof(f));

     for(i=;i<m;i++) scanf("%d%d",&a,&b), f[a][b]=;

     for(i=;i<=n;i++)

     {

         memset(mark,,sizeof(mark));  flag=;

         bfs(i);

         if(flag)

             printf("T\n");

         else

             printf("F\n");

     }

     return ;

 }

看了题解，发现有人用Floyd ，主要是数据量小，orz

AC代码：

 #include <cstdio>

 #include <iostream>

 #include <cstring>

 int f[][];

 int n,m,x,y;

 using namespace std;

 int main()

 {

      scanf("%d%d",&n,&m);

      memset(f ,  , sizeof(f));

         for(int i = ;i <= m;++ i){

          scanf("%d%d",&x,&y);

          f[x][y] = ;

      }

      for(int k = ;k <= n;++ k)

          for(int i = ;i <= n;++ i)

              for(int j = ;j <= n;++ j)

                   if(f[i][k] ==  && f[k][j] == )

                         f[i][j] = ;

      for(int i = ;i <= n;++ i)

          if(f[i][i] == )

               cout<<"T"<<endl;

           else

               cout<<"F"<<endl;

      return ;

 }

传话

codevs 1506 传话

http://codevs.cn/problem/1506/

1506 传话