博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
POJ 3180 Tarjan
阅读量:6868 次
发布时间:2019-06-26

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

题意:找强连通中点数大于2的强连通分量个数

思路:Tarjan

// By SiriusRen #include 
#include
using namespace std;int n,m,ans=0,t=0,cnt=0,tot=1,top=0,dfn[50050],low[50050],p[10050],s[10050];int xx,yy,jy,first[10050],next[50050],v[50050];bool vis[50050];void add(int x,int y){v[tot]=y;next[tot]=first[x];first[x]=tot++;}void tarjan(int x){ dfn[x]=low[x]=++cnt;vis[x]=1,s[++top]=x; for(int i=first[x];i;i=next[i]) if(!dfn[v[i]])tarjan(v[i]),low[x]=min(low[x],low[v[i]]); else if(vis[v[i]])low[x]=min(low[x],dfn[v[i]]); if(dfn[x]==low[x]){t++;do jy=s[top--],vis[jy]=0,p[t]++;while(jy!=x);}}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++)scanf("%d%d",&xx,&yy),add(xx,yy); for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i); for(int i=1;i<=n;i++)if(p[i]>=2)ans++; printf("%d\n",ans);}

转载于:https://www.cnblogs.com/SiriusRen/p/6532366.html

你可能感兴趣的文章
Linux磁盘分区实战案例
查看>>
squid 3.2 的高级应用-用户认证
查看>>
01_Linux学习
查看>>
修改win 7用户配置文件临时为本地!
查看>>
我的友情链接
查看>>
Apache静态缓存配置
查看>>
牛刀小试之 ---文本处理工具之 grep egrep用法
查看>>
我的友情链接
查看>>
杭电 hdu 2017
查看>>
HashMap与ConcurrentHashMap的区别
查看>>
深入理解Android消息处理系统——Looper、Handler、Thread
查看>>
我的友情链接
查看>>
标准日本语 04_005
查看>>
2013.7.16
查看>>
LVM管理:如何强制删除卷组(volumn group)
查看>>
linux ps 命令(每日一令之二十七)
查看>>
设计模式之策略模式
查看>>
HDFS简介
查看>>
Android移动应用界面的模板化设计
查看>>
linux大文件切割成多个小文件
查看>>