#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 10000
using namespace std;
int x,y,n,m,t,tot,sum,top,time;
int head[N],col[N],stack[N],dfn[N],low[N],a[N][N];
bool vis[N];
struct Edge
{
int from,next,to;
}edge[N];
int add(int x,int y)
{
tot++;
edge[tot].to=y;
edge[tot].next=head[x];
head[x]=tot;
}
int read()
{
int x=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return f*x;
}
int tarjan(int now)
{
//stack[]表示递归过程的栈,即用来判断该点是否已经加入到此次递归的栈中,在递归末尾,通过将vis置为false释放所有递归栈的元素
t=;
dfn[now]=low[now]=++time;//初始每一个点的low值dfn等于它的时间戳
stack[++top]=now; vis[now]=true;//将该点入栈,标记为在栈中
for(int i=head[now];i;i=edge[i].next)//更新于他相连的点的low值
{
x=edge[i].to;
if(vis[x]) low[now]=min(dfn[x],low[now]);//如果该点已经在栈中,直接更新来到该点的那个点的low,不需要递归查询
else if(!dfn[x])
{
tarjan(x);
low[now]=min(low[x],low[now]);//不在栈中,需要从该点继续递归拓展
}
}
if(low[now]==dfn[now])//说明以这个点结束强连通分量
{
sum++;// 强连通分量的个数加一
col[now]=sum;//将该点放在她所属的强连通分量了
for(;stack[top]!=now;top--)
{
col[stack[top]]=sum;
vis[stack[top]]=false;
}
vis[now]=false;
top--;
}
}
int main()
{
n=read(),m=read();
for(int i=;i<=m;i++)
{
x=read();y=read();
add(x,y);
}
for(int i=;i<=n;i++)
if(!dfn[i]) tarjan(i);
printf("%d",sum);
return ;
}

最新文章

  1. Java进击C#——前言
  2. Refresh recovery area usage data after manually deleting files under recovery area
  3. Xshell快捷键
  4. HDU 2586 LCA
  5. oracle日志总结
  6. 转: Android开发中的MVP架构详解(附加链接比较不错)
  7. Chrome的隐身模式
  8. Recommended add-ons/plugins for Microsoft Visual Studio
  9. android 客户端 和 新浪微博如何打通的
  10. 静默安装ORACLE【weber出品必属精品】
  11. OpenGLES 怎样在十天内掌握线性代数 - 希望这是真的!
  12. 一些常用的jquery数字正则表达式
  13. 「mysql优化专题」90%程序员没听过的存储过程和存储函数教学(7)
  14. iOS XML解析使用-韩国庆
  15. 著名的Log4j是怎么来的?
  16. Jexus 网站服务器和 ASP.NET 跨平台开发
  17. 学习笔记&lt;3&gt;View接触
  18. MapReduce Demo
  19. Java 8- Java 分支结构 - if…else/switch
  20. OpenUDID 实现UDID替代

热门文章

  1. Redis之有序集合命令
  2. centos7: svbversion版本的安装配置+tortoisesvn登录验证
  3. php程序突然不能用file_get_contents()访问远程网址了?
  4. tryparse
  5. .net 获取邮箱邮件列表和内容
  6. (转)不要自称是程序员,我十多年的 IT 职场总结
  7. python怎样压缩和解压缩ZIP文件
  8. English trip -- VC(情景课) 6 D
  9. 谈谈http与https
  10. Android之RecyclerView实现时光轴