用刚搞到的模板，去过了一道题 差不多是个模板题 有一群奶牛，奶牛A可以关注B，关注具有传递性，给出奶牛之间的关注关系，问有几只奶牛得到了所有其他奶牛的关注？ 互相关注的可以看成一个点，所以直接tarjan算法 + 缩点 新图中，出度为0的点只能有一个，因为如果有两个，这两个新点（原连通分量）就一定是互相没有关注联系的 然后答案就是这个出度为0 的新点（原连通分量）中包含的原来点的个

http://poj.org/problem?id=2186 题意：有n头牛，m个膜拜关系，膜拜关系是不可逆的而且是单向传递的，比如A膜拜B，B膜拜C,那么A也膜拜C，但B不一定膜拜A。最后问有多少头牛满足条件：除了它自己，其他所有的牛都膜拜它。 思路： 问题可以抽象为：给定一个有向图，n个顶点，m条有向边，有多少个顶点满足：其他所有的点都能到达该点。 首先假如图G是一个有向树

题目地址：POJ 2186 先用强连通分量缩点，然后形成一棵树。我第一次用的判定条件是入度为分量数-1。虽然这种情况下确实正确。但是在树中也是有间接关系的。这个条件并不是充分必要条件。正确的做法是逆序建树，然后找根结点。而且根结点有且只有一个才可以。所以转化成了找出度为0的分量。 代码如下： #include <iostream>#include <string.h>#include

http://poj.org/problem?id=2186 我们求强连通分量时，给每个顶点做一个标记，标记该顶点属于哪个强联通分量，然后属于同一个强连通分量的点就可以看作同一个点了。这就是所谓的“缩点”   此题用了个定理 ：有向无环图（DAG）中，从任意一个点出发，必定可以到达某一个出度为0的点。   这个不用证明，直观想一下就行了。  因为无环，所以从一个点出发，必

这道题是求最强连通分量，将图压缩，即属于一个强连通分量的所有点变成一个点，然后看出度为0的点有多少个。因为最popular的牛不应该有出去的边，反之亦成立。如果我们只有一个点（压缩点）没有出度，那么输出这个压缩点所代表的所有点，即属于这个强连通分量的所有点。这些牛是等效的。否则，多于一个点没有出度，这时图是不连通的，输出0。不可能没有出度为0的点(a little hard to explain)

首先是一些知识整理：来源于网络： 以下转载于：http://blog.sina.com.cn/s/blog_4dff87120100r58c.html   Kosaraju算法是求解有向图强连通分量（strong connectedcomponent）的三个著名算法之一，能在线性时间求解出一个图的强分量。 什么是强连通分量？在这之前先定义一个强连通性（strong connectivi

原题复刻 思想的火花 ： 首先要层序操作是什么意思，题主就使用了STL中的queue来做，关注函数的书写规则，被‘&’和'*'两种操作搞了半天。 #include<iostream>#include<queue>using namespace std;struct node{char data;struct node *l,*r;};void built(nod

做法： 把图中所有的圈缩成一个点，那么就是求是否存在一个点，使得所有的点都能到达。 遍历所有入度为0的点，对所有遍历到的出度为0的点的标记+1； 若出度为0的点的数目大于两个，则输出0。否则若标记的值等于入度点的和，那么输出这个点缩点之前含的点。 #include<stdio.h>#include<iostream>#include<string.h>#include<alg

Problem Description 当抢救人员发现她的时候，她已经死了，是被垮塌下来的房子压死的，透过那一堆废墟的的间隙可以看到她死亡的姿势，双膝跪着，整个上身向前匍匐着，双手扶着地支撑着身体，有些象古人行跪拜礼，只是身体被压的变形了。救援人员从废墟的空隙伸手进去确认了她已经死亡，又在冲着废墟喊了几声，用撬棍在在砖头上敲了几下，里面没有任何回应。 当人群走到下一个建筑物的时候，救援队长忽然往

n>=m,所以就变成了求 ϕ(m!)∗n!/m! \phi(m!)*n!/m! 而 ϕ(m!)=m!∗(p−1)/p...... \phi(m!)=m!*(p-1)/p......p为m!的素因子,即为m内的所有素数,问题就转化为了求 n!∗(p−1)/p...... n!*(p-1)/p...... 只需要预处理出素数，阶乘，逆元即可 #inc