poj2186专题

SCC::poj2186 Popupar Cows poj2553 The Bottom of A Graph

关于SCC的知识与算法,参见《SCC》一文。这两道题本质是一样的,细微的区别只在于输出而已。夜鱼只给我做前一道题,大概是看到我做的《图算法》的小结里面没有SCC的地位,想给我提个醒。后来我在那篇小结里面补上了SCC,顺便也对SCC的知识梳理了一遍,觉得手痒,网上查了一下还有poj2553也是关于SCC的,但没想到poj2553一题是赤裸裸的SCC,但这道题我却WA了几次,原因是在输出的时候没有“按

POJ2186 Popular Cows(强连通分量)

题意: 奶牛A觉得奶牛B流行,奶牛B觉得奶牛C流行,则奶牛A也觉得奶牛C流行,现在要统计被其他所有奶牛觉得流行的奶牛数量。 要点: 先求出强连通分量并缩成点,算出对应入度和出度,统计出度为0的奶牛数即可,一开始我是统计进度为cnt-1的,后来发现WA,错误的地方在题目里也说了,A->B->C这种也认为A觉得C流行,所以不能用入度算,只能计算出度为0的点,而且如果有好几个点出度为0要输出0