Tarjan强联通分量【模板】
2024-08-31 12:21:34
#include <algorithm>
#include <cstdio> using namespace std; const int N();
int n,m,v,u;
int edgesum,head[N]; struct Edge
{
int from,to,next;
Edge(int from=,int to=,int next=) :
from(from),to(to),next(next) {}
}edge[N];
int ins(int from,int to)
{
edge[++edgesum]=Edge(from,to,head[from]);
return head[from]=edgesum;
} int dfn[N],tim,low[N],vis[N];
int Stack[N],top,instack[N];
int col[N],colsum; void DFS(int now)
{
dfn[now]=low[now]=++tim; vis[now]=;
Stack[++top]=now; instack[now]=;
for(int i=head[now];i;i=edge[i].next)
{
int to=edge[i].to;
if(instack[to]) low[i]=min(low[i],dfn[to]);
else if(!vis[to])
DFS(to),low[i]=min(low[i],low[to]);
}
if(low[now]==dfn[now])
{
colsum++;
col[now]=colsum;
for(;Stack[top]!=now;top--)
{
col[Stack[top]]=colsum;
instack[Stack[top]]=;
}
instack[now]=;
top--;
}
} int main()
{
scanf("%d%d",&n,&m);
for(;m--;)
{
scanf("%d%d",&u,&v);
ins(u,v);
}
for(int i=;i<=n;i++)
if(!vis[i]) DFS(i);
return ;
}
最新文章
- Markdown语法
- Windows 搭建 .NET 跨平台环境并运行应用程序
- Shell 的变量功能
- PHP编译支持mysqli
- JBOSS /invoker/JMXInvokerServlet 利用工具 .
- Python中pip版本升级error:You are using pip version 7.1.2, however version 8.1.1 is available.
- Oracle数据库中char, varchar, nvarchar的差异
- JS 去除字符串中的空格
- thinkphp显示重复两次
- iPhone 7-b
- java 多线程下载
- React 深入系列3:Props 和 State
- 在linux系统中I/O 调度的选择
- .Net Core应用框架Util介绍(六)
- Zabbix 3.0的前端默认在Centos 6上不支持
- Centos7防火墙快速开放端口配置方法
- javascript作用域、闭包、对象与原型链
- Java冒泡排序与选择排序
- Win7 搭建pptpvpn服务器方法
- JS如何获取PHP循环中的ID
热门文章
- java import跨包引用类理解
- [Performance] Optimize Paint and Composite for the website
- crm2013使用图片字段
- Oozie4.2.0配置安装实战
- Android 四大组件学习之ContentProvider三
- UVA 11609 - Anne&#39;s game cayley定理
- 浅析PHP中cookie与session技术
- 项目部署在windows下的tomcat里
- 编译最新版webrtc源码和编译好的整个项目10多个G【分享】
- vue中 router-link 传递参数以及获取