bzoj1051Tarjan裸题
2024-08-25 06:28:56
tarjan缩点+判断出度为0的点
所以不需要新建边
#include <cstdio>
int n,m,p,q,N=,time=,T=,sum=,ans=;
int from[],to[],nex[],fir[],dfn[],low[],l[],tar[],gui[],c[];
bool que[];
void add(int p,int q){ from[++N]=p,to[N]=q,nex[N]=fir[p],fir[p]=N;}
int min(int p,int q){ return (p<q)?p:q;}
void dfs(int k)
{
dfn[k]=low[k]=++time,l[++T]=k,que[k]=;
for(int o=fir[k];o;o=nex[o])
if(!dfn[to[o]])
dfs(to[o]),low[k]=min(low[k],low[to[o]]);
else
if(que[to[o]])
low[k]=min(low[k],dfn[to[o]]);
if(dfn[k]==low[k])
{
sum++;
while(l[T]!=k)
que[l[T]]=,tar[l[T--]]=sum,gui[sum]++;
que[k]=;tar[k]=sum;T--;gui[sum]++;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
scanf("%d%d",&p,&q),add(p,q);
for(int i=;i<=n;i++)
if(!dfn[i]) dfs(i);
for(int i=;i<=N;i++)
if(tar[from[i]]!=tar[to[i]])
c[tar[from[i]]]=;
for(int i=;i<=sum;i++)
if(!c[i])
if(ans){ printf("0\n");return ;}
else ans=gui[i];
printf("%d\n",ans);
return ;
}
tarjan差点写错,心碎
最新文章
- WEB页面中常见的四种控件的必须的测试
- git常用的命令集合
- 认识WCF
- SQL_函数
- 浅析Dagger2的使用
- UVa 109 - SCUD Busters(凸包计算)
- 为什么 Node.js 这么火,而同样异步模式 Python 框架 Twisted 却十几年一直不温不火?
- PHP 上传图片和安全处理
- 图像处理之image stitching
- 【MySQL】MySQL锁和隔离级别浅析二 之 INSERT
- JS正则表达式基础总结
- 剑指OFFER之用两个栈实现队列(九度OJ1512)
- chrome中安装.crx后缀的离线插件
- JavaSrcipt的数字(number):深入理解内部机制
- redis-set
- Python开发——【条件】语句
- Redis学习笔记--Redis数据过期策略详解==转
- 如何下载网易云音乐APP里的MV和短视频?
- The each() function is deprecated报错的解决方法
- ubuntu设置IP地址、网关的方法
热门文章
- 数组中的每一个对象执行一次方法:makeObjectsPerformSelector
- Java transient 关键字
- 53. 特殊的O(n)时间排序[sort ages with hashtable]
- iOS CoreData 中 objectID 的不变性
- ServiceStack.Redis订阅发布服务的调用(Z)
- 我的CPG插件 (什么是CPG,就是跟号称全球唯一C++编写的魔镜是一样的格式的)
- Tern Sercer Tineout
- 在Nodejs中如何调用C#的代码
- Maven之安装与简单入门一
- 51nod1134(最长递增子序列)