题意:牛A喜欢牛B,若牛B喜欢牛C,则牛A喜欢牛C,问最后多少牛被其它全部牛喜欢
思路:用强联通分量进行缩点,最后形成的图是有向无环图DAG。而拓扑序的值为DAG的长度,则加一,可是最后我们要推断一下这些牛是不是被全部牛喜欢,由于等于DAG长度的全部点肯定是一个强联通分量,因此它们能够相互喜欢,我们用当中一仅仅牛推断即可了,推断时就用反向边推断这个牛能不能到达其它的牛即可了
#include#include #include #include #include #include using namespace std;typedef long long ll;const int inf=0x3f3f3f3f;const int maxn=10010;int V;vector G[maxn];vector rG[maxn];vector vs;bool used[maxn];int cmp[maxn];void add_edge(int from,int to){ G[from].push_back(to); rG[to].push_back(from);}void dfs(int v){ used[v]=1; for(unsigned int i=0;i =0;i--){ if(!used[vs[i]]) rdfs(vs[i],sum++); } return sum;}int main(){ int m; while(scanf("%d%d",&V,&m)!=-1){ for(int i=0;i
posted on 2017-08-15 09:30 阅读( ...) 评论( ...)