• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ2186 – Popular Cows

    ACM-POJ EXP 159阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意

    有N只奶牛,其中奶牛A认为奶牛B备受注目,而奶牛B也可能认为奶牛C备受注目。奶牛们的这种“认为”是单向可传递的,就是说若奶牛A认为奶牛B备受注目,但奶牛B不一定会认为奶牛A备受注目。而当A认为B备受注目,且B认为C备受注目时,A一定也认为C备受注目。

    现在给出M对这样的“认为…备受注目”的关系对,问有多少只奶牛被除其本身以外的所有奶牛关注。

    解题思路

    极大强连通分量+缩点

    发现自从用Tarjan算法做了 POJ2942 之后,这些利用Tarjan算法的题目都是水题。

    构造模型

    N个顶点的有向图G,有M条边。求一共有多少个点,满足这样的条件:所有其它的点都可以到达这个点。

    首先,这个题的N和M都非常大,暴搜肯定TLE。

    考虑一下,如果图G是一棵有向树,那么问题就变的很简单了,因为当且仅当这棵树只有一个叶子结点(出度为0的点)时,树上的其他所有结点都能到达这个点。而当有向树上有1个以上的叶子时,都是无解的。

    由于树是无环的,下面称这样的一棵有向树为 有向无环树DAG


    那么我们能否把图转化为树去求解呢

    首先可以想到的是,如果图G中包含有环,那么就可以把这个环缩成一个点,因为环中的任意两个点可以到达,环中所有的点具有相同的性质,即它们分别能到达的点集都是相同的,能够到达它们的点集也是相同的。

    那么是否只有环中的点才具有相同的性质呢?进一步的考虑,图中的每一个极大强连通分量中的点都具有相同的性质。所以,如果把图中的所有极大强连通分量求出后,对每个极大强连通分量缩点,就可以把图收缩成一棵有向无环树DAG,那么只要判断出度为0的缩点是否只有1个,若DAG中有且仅有1个这样的缩点,则输出缩点(图G的极大强连通分量)内所包含的图G的结点个数,问题就解决。


    预备知识:Tarjan算法求有向图的极大强连通分量

    补充一个小内容:

    用Tarjan算法求极大强连通分量时,对于有向边s->t

    1、 若DFN[t]==0,则s->t是一条树边,t尚未入栈;

    2、 若DFN[t]<DFN[s],当t在栈中,s->t为一条后向边;当t已经出栈,s->t为一条横叉边。

    注意只有有向图有横叉边,无向图不存在横叉边的概念。

    对横叉边的处理:无视掉。

    Source修正

    USACO 2003 Fall (已失效)


    转载请注明:EXP 技术分享博客 » POJ2186 – Popular Cows

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址