tarjan强连通分量 (模板)
2024-09-06 06:13:47
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN = 10005;
struct Edge{
int nxt,to;
}edge[10*MAXN];
int n,m,stack[MAXN],low[MAXN],dfn[MAXN];
int cnt,head[MAXN],col[MAXN],num,top,col_num;
bool vis[MAXN];
inline void add(int bg,int ed){
edge[++cnt].to=ed;
edge[cnt].nxt=head[bg];
head[bg]=cnt;
}
inline void tarjan(int u){
dfn[u]=low[u]=++num;
vis[u]=1;
stack[++top]=u;
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[v],low[u]);
}
else if(vis[v])
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
vis[u]=0;
col[u]=++col_num;
while(stack[top]!=u){
col[stack[top]]=col_num;
printf("%d ",stack[top]);
vis[stack[top--]]=0;
}
printf("%d\n",u);
top--;
}
}
int main(){
scanf("%d%d",&n,&m);
for(register int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
}
for(register int i=1;i<=n;i++){
if(!dfn[i]) tarjan(i);
}
}
最新文章
- Ioc和Ao使用扩展
- Android Studio获取SHA1和MD5方法
- DOM元素querySelectorAll可能让你意外的特性表现
- ipcs, ipcrm
- css整理-06 表和列表
- IOS第15天(2,事件处理,侧滑菜单,抽屉效果)
- linux /usr/bin/ld: cannot find -lxxx
- 命令行导入SQL文件
- 他们在军训,我在搞 OI(一)
- Archlinux 简明安装指南
- A Framework for Programme Management
- LinearLayout增加divider分割线
- mysql校对规则引起的不区分大小写
- myBatis 基础测试 表关联关系配置 集合 测试
- 超越村后端开发(3:安装djangorestframework+序列化+API开发前期准备)
- 记录Vim常用命令
- mac 开发新户攻略-brew
- 1283: 骨牌铺方格(zzuli)
- 简单理解Zookeeper的Leader选举【转】
- 自己实现字符串转整数(不使用JDK的字符串转整数的方法)