题目名称 1001. [WZOI2011 S3] 消息传递
输入输出 messagew.in/out
难度等级 ★★
时间限制 1000 ms (1 s)
内存限制 128 MB
测试数据 10 简单对比
题目来源 2012-08-09
开放分组 全部用户
提交状态
分类标签
连通性 强连通分量
通过:200, 提交:651, 通过率:30.72%
Gravatar梦那边的美好ET 100 0.107 s C++
Gravatarhzoi2017_nzy 100 0.129 s C++
Gravatarnew ioer 100 0.173 s C++
Gravatarnew ioer 100 0.185 s C++
GravatarAAAAAAAAAA 100 0.203 s C++
GravatarFuryton 100 0.213 s C++
GravatarFuryton 100 0.214 s C++
Gravatarbbsh 100 0.219 s C++
GravatarAPWTMECRD 100 0.220 s C++
Gravatar521 100 0.221 s C++
关于 消息传递 的讨论
好久没写过强连通了= =....两遍dfs慢死...
Gravatarraywzy
2013-10-26 16:27 1楼
在一个多于1个点的SCC中,每个点都一定可以传回自己
证明:A、B同时属于V这个SCC中,根据SCC性质,必定存在A->B一条通路;由于是单向通路,必定也存在B->A的通路,那么A可以传回A,B可以传回B。
在两个不同的SCC中,两个点分别在两个SCC中一定不可以传回自己
证明:A属于V1,利用反证:如果存在B属于V2满足A->B、B->A这两条通路,那么对于任意一点C属于V1都有C->A->B、B->A->C,所以根据SCC性质,V1与V2可以合并。
至此本题可以转换为:整理SCC,对于节点数>1的SCC内的所有点都输出T,否则输出F
Gravatardigital-T
2013-10-28 16:56 2楼
注意有些点不连通的情况。。。:(
GravatarChenyao2333
2014-02-09 16:13 3楼
回复 @digital-T :
见证学霸的养成=v=
Gravatar笑一炮
2014-10-25 17:43 4楼
我放弃了
Gravatar乌龙猹
2014-10-27 20:51 5楼
又一次遇见了无端WWWWWWWWWW的情况
Gravatarztx
2014-11-05 16:14 6楼
蛤蛤,我终于会写强连通辣→_→
GravatarAsm.Def
2015-06-30 13:40 7楼
Gravatar旧梦
2015-07-24 11:32 8楼
Gravatarforever
2015-07-25 11:13 9楼
tarjan练手
Gravatarliu_runda
2016-01-22 10:56 10楼
0.0
GravatarRiolu
2016-04-03 18:17 11楼
第一道强连通分量Get~~~
GravatarMarvolo
2016-04-15 12:59 12楼
这道题用DFS直接删边处理会有且仅有一个数据的一个点不对,希望大神拯救我破灭的代码!
GravatarYGOI_真神名曰驴蛋蛋
2016-05-19 12:16 13楼
出门右转=>下河
GravatarSky_miner
2016-05-21 17:51 14楼
哎~~小错误层出不清
果然还是我太弱。
GravatarMagic_Sheep
2016-05-26 10:25 15楼
用一个漂亮的AK来作为跻身前一百的通行证!
happy~~
Gravatar浮生随想
2016-09-04 21:27 16楼
双倍经验!!
GravatarWeiSama
2017-03-12 10:25 17楼
出门左转PID 619双倍经验
出门右转PID 921有机会获得三倍经验
PS:蒟蒻数据无力吐槽...说好的重边呢2333333没判重一样A掉了(手动滑稽)
Gravatarrvalue
2017-02-18 14:55 18楼
骗人。。
文件明明是messagew.in/messagew.out
GravatarLunardrop
2017-03-29 12:35 19楼
......
GravatarFisher.
2017-08-06 14:51 20楼
200斩!
GravatarkZime
2017-08-15 16:05 21楼
tarjan模板题
Gravatar小红红
2019-02-20 20:43 22楼
双倍经验转619。
Gravatarleon
2019-07-11 23:06 23楼
QAQ这也太简单了吧
Gravatar李俊辉
2019-08-10 20:13 24楼

1001. [WZOI2011 S3] 消息传递

★★   输入文件:messagew.in   输出文件:messagew.out   简单对比
时间限制:1 s   内存限制:128 MB
Problem 2 消息传递 (messagew.pas/c/cpp)
问题描述
WZland开办了一个俱乐部(这里面可以干任何的事情),这引来了许多的人来加入。俱乐部的人数越来越多,关系也越来越复杂……
俱乐部的人来自各个地方,为了增加友谊,俱乐部举行了一次晚会。晚会上又进行了一个传话游戏,如果A认识B,那么A收到某个消息,就会把这个消息传给B,以及所有A认识的人(如果A认识B,B不一定认识A),所有人从1到N编号。
现在给出所有“认识”关系,俱乐部的负责人WZland的国王想知道一个十分简单的问题:如果A发布一条新消息,那么会不会经过若干次传话后,这个消息传回给了A,1≤A≤N。但是WZland的国王是出了名的数学差,幸好的是你在他的身边,于是他就将这个问题交给你来解决。


输入格式
输入数据中的第一行是两个数N和M,两数之间有一个空格,表示人数和认识关系数。
接下来的M行,每行两个数A和B,表示A认识B(1A, BN,AB)。
输出格式
输出文件中一共有N行,每行一个字符“T”或“F”。第i行如果是“T”,表示i发出一条新消息会传回给i;如果是“F”,表示i发出一条新消息不会传回给i。
样例输入输出
messagwe.in 
4 6
1 2
2 3
4 1
3 1
1 3
2 3
messagew.out
T
T
T
F


数据规模
对于30%的数据,N≤1000,M≤20000;
对于50%的数据,N≤10000,M≤100000;
对于100%的数据,N≤100000,M≤200000;
认识关系可能会重复给出。
时间限制
1s