hdu1269 Tarjan强连通分量 模板(转)
2024-10-21 05:42:20
#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
const int maxn=;
vector<int>g[maxn]; int Bcnt;
int Top;
int Index;
int low[maxn],dfn[maxn];
int belong[maxn],stack[maxn];
int instack[maxn]; void Init_tarjan(int n)
{
Bcnt=Top=Index=;
for(int i=;i<=n;i++)
low[i]=dfn[i]=;
}
void Tarjan(int u)
{
stack[Top++]=u;
instack[u]=;
low[u]=dfn[u]=++Index;
for(int i=;i<g[u].size();i++)
{
int v=g[u][i];
if(!dfn[v])
{
Tarjan(v);
low[u]=min(low[v],low[u]);
}
else
{
if(instack[v])
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u])
{
++Bcnt;
int v;
do
{
v=stack[--Top];
instack[v]=;
belong[v]=Bcnt;
}
while(u!=v);
} }
int main()
{
int n,m;
int i;
int x,y;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==&&m==)break;
for(i=;i<=n;i++)
g[i].clear();
while(m--)
{
scanf("%d %d",&x,&y);
g[x].push_back(y);
}
Init_tarjan(n);
for(i=;i<=n;i++)
{
if(!dfn[i])
Tarjan();
}
if(Bcnt==)printf("Yes\n");
else printf("No\n");
}
return ;
}
最新文章
- 在linux上安装psycopg2出错--Error: pg_config executable not found.
- lintcode:整数排序||
- iOS开发网络篇—大文件的多线程断点下载(转)
- ZedGrap控件绘制图表曲线
- css居中技巧
- android设置图片变化的四种效果代码
- Android Studio 调试过程中快捷查看断点处变量值(Ctrl+Shift+I无效)?
- 乐在其中设计模式(C#) - 模板方法模式(Template Method Pattern)
- 告诉你 IOS9.0 之后的Bitcode到底是什么!!
- (java web后端方向)如何让你的简历为你争取到更多的面试机会,内容来自java web轻量级开发面试教程
- python黑科技:还在为没有wifi而烦心吗?这篇文章解决你的困扰
- nginx学习笔记(二)
- oracle存储过程---创建存储过程语句
- 空串、null串和isEmpty方法
- vue-cli脚手架之webpack.test.conf.js
- putty 链接亚马逊服务器
- 知乎网的CSS命名规律研究
- P2651 添加括号III
- js模拟点击打开超链接
- A Simple Problem with Integers---poj3468线段树