博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
POJ 2186 强联通分量
阅读量:5348 次
发布时间:2019-06-15

本文共 925 字,大约阅读时间需要 3 分钟。

题意:牛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 阅读(
...) 评论(
...)

转载于:https://www.cnblogs.com/mthoutai/p/7363372.html

你可能感兴趣的文章
[Python学习] 简单网络爬虫抓取博客文章及思想介绍
查看>>
触发器课程SQL Server 知识梳理九 触发器的使用
查看>>
信息浏览器从Android的浏览器中传递cookie数据到App中信息浏览器
查看>>
客户端连接linux虚拟机集群报错
查看>>
linux下部署一个JavaEE项目的简单步骤
查看>>
hash储存机制
查看>>
[Android学习系列16]Android把php输出的json加载到listview
查看>>
20145205 《信息安全系统设计基础》第14周学习总结
查看>>
6)添加一个窗口的图标
查看>>
POJ - 1422 Air Raid 二分图最大匹配
查看>>
Road Map
查看>>
正则替换中的一个Bug
查看>>
HI3531uboot开机画面 分类: arm-linux-Ubunt...
查看>>
制作U盘启动CDLinux 分类: 生活百科 ...
查看>>
strcpy函数里的小九九
查看>>
搭建ssm过程中遇到的问题集
查看>>
OpenLayers绘制图形
查看>>
tp5集合h5 wap和公众号支付
查看>>
Flutter学习笔记(一)
查看>>
iOS10 国行iPhone联网权限问题处理
查看>>