Gravatar
笑一炮
积分:200
提交:54 / 134
回复 @digital-T :
见证学霸的养成=v=

Gravatar
Chenyao2333
积分:770
提交:122 / 365
注意有些点不连通的情况。。。:(

Gravatar
digital-T
积分:2213
提交:586 / 1311
在一个多于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

Gravatar
raywzy
积分:713
提交:238 / 509
好久没写过强连通了= =....两遍dfs慢死...