首页 > 代码库 > hdu1269 Tarjan强连通分量 模板(转)
hdu1269 Tarjan强连通分量 模板(转)
#include<stdio.h>#include<iostream>#include<vector>using namespace std;const int maxn=10010;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=0; for(int i=0;i<=n;i++) low[i]=dfn[i]=0;}void Tarjan(int u){ stack[Top++]=u; instack[u]=1; low[u]=dfn[u]=++Index; for(int i=0;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]=0; 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==0&&m==0)break; for(i=1;i<=n;i++) g[i].clear(); while(m--) { scanf("%d %d",&x,&y); g[x].push_back(y); } Init_tarjan(n); for(i=0;i<=n;i++) { if(!dfn[i]) Tarjan(1); } if(Bcnt==1)printf("Yes\n"); else printf("No\n"); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。