题目 1001 [WZOI 2011 S3] 消息传递
2014-10-25 17:43:55
|
|
注意有些点不连通的情况。。。:(
|
|
在一个多于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
题目 1001 [WZOI 2011 S3] 消息传递
2013-10-28 16:56:40
|
|
好久没写过强连通了= =....两遍dfs慢死...
|