Codevs 1506 传话:一个朋友网络,如果 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 Input4 6
1 2
2 3
4 1
3 1
1 3
2 3
样例输出 Sample OutputT
T
T
F
数据范围及提示 Data Size & Hintn<=10001<=a, b<=n
分析:1. 能连成图 2.a 能否(间接)到 a:a 既当起点也当终点考虑用最短路【k:相当于间接找】
代码
- #include#includeusing namespace std;
- int n,
- m;
- int a,
- b;
- int fa[1001][1001];
- int main() {
- scanf("%d%d", &n, &m);
- for (int i = 1; i <= m; i++) {
- scanf("%d%d", &a, &b);
- fa[a][b] = 1;
- } //找 for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(fa[i][k]==1&&fa[k][j]==1) fa[i][j]=1; for(int i=1;i<=n;i++) { if(fa[i][i]==1) cout<<"T"<
就爱阅读 www.92to.com 网友整理上传, 为您提供最全的知识大全, 期待您的分享,转载请注明出处。
来源: http://www.92to.com/bangong/2017/04-10/20250280.html