博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
poj 2186: Popular Cows(tarjan基础题)
阅读量:6294 次
发布时间:2019-06-22

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

题意:求在图上可以被所有点到达的点的数量。

首先通过tarjan缩点,将所有内部两两可达的子图缩为一点,新图即为一个有向无环图(即DAG)。

在这个DAG上,若存在不止一个所有点均可到达的点,则所有点不满足题目要求。若存在一个,则该点所代表的连通分量的点数即为答案。

//DAG(有向无环图)上面至少存在一个出度为0的点,否则必然可以成环。

#include
#include
#include
#include
using namespace std;typedef long long LL;const int N=10007;int n,m;vector
adj[N];int time_tag;int dfn[N]; // dfs序int low[N]; // low[u]表示u及其后代所能追溯到的最早的祖先点v的dfn[v]值 int sccno[N];int scc_cnt; int size[N]; //size[i]表示编号为i的连通分量的大小int d[N]; //d[i]==0时表示,编号为i的连通分量不认为任何其他分量popular stack
st;void init(){ time_tag=scc_cnt=0; memset(sccno,0,sizeof(sccno)); memset(dfn,0,sizeof(dfn)); for(int i=1;i<=n;i++) adj[i].clear(); memset(d,0,sizeof(d));}void dfs(int u){ dfn[u]=low[u]=++time_tag; st.push(u); for(int i=0;i

 

转载于:https://www.cnblogs.com/Just--Do--It/p/6442136.html

你可能感兴趣的文章
vue过渡和animate.css结合使用
查看>>
C#编程(七十四)----------释放非托管资源
查看>>
如何在Java 环境下使用 HTTP 协议收发 MQ 消息
查看>>
java-容器-ArrayList
查看>>
集合体系
查看>>
RocketMQ与Kafka对比(18项差异)
查看>>
Android学习--------实现增删改查数据库操作以及实现相似微信好友对话管理操作...
查看>>
兔子--eclipse设置编码格式
查看>>
[转]程序集之GAC---Global Assembly Cache
查看>>
英语词汇(5)followed by / sung by / written by
查看>>
HDFS Namenode启动过程
查看>>
SQL Server查询某个字段存在哪些表中
查看>>
web实现QQ第三方登录 开放平台-web实现QQ第三方登录
查看>>
【划分树+二分】HDU 4417 Super Mario
查看>>
WPF 基础到企业应用系列1——开篇故意
查看>>
Android - TextureView, SurfaceView和GLSurfaceView 以及 SurfaceTexture
查看>>
【GoldenGate】使用OGG,两个Oracle库之间单向同步数据
查看>>
Jenkins构建完成后通过SVN Publisher Plugin上传文件到指定的SVN(教程收集)
查看>>
10-01 Java 类,抽象类,接口的综合小练习--运动员和教练
查看>>
一级域名和二级域名的区别是什么?作用怎样?
查看>>