首页 > 代码库 > HDU 1269 裸奔的强联通分量
HDU 1269 裸奔的强联通分量
看了别人博客 http://blog.csdn.net/jokes000/article/details/7538994
#include <cstdio>#include <cmath>#include <algorithm>#include <iostream>#include <cstdlib>#include <string>#include <queue>#include <stack>#include <cstring>#define CL(a,b) memset(a,b,sizeof(a))#define ll __int64#define TEST cout<<"TEST ***"<<endl;#define INF 0x7ffffff0#define MOD 1000000007using namespace std;typedef struct myedge{ int e,next;}E;E edge[100010];stack <int> st;int head[10010],ct,tim;int ti[10010],lo[10010],ins[10010],n,m;void inithead(){ CL(head,-1); tim=0; ct=0;}void addedge(int s,int e){ edge[ct].e=e;edge[ct].next=head[s];head[s]=ct++;}void targan(int i){ tim++; ti[i]=tim;lo[i]=tim; st.push(i); ins[i]=1; int p=head[i]; int v; while(p!=-1) { v=edge[p].e; if(ins[v]==1) { lo[i]=min(lo[v],lo[i]); } else if(ti[v]==0) { targan(v); lo[i]=min(lo[i],lo[v]); } p=edge[p].next; } if(lo[i]==ti[i]) { while(!st.empty()&&lo[st.top()]==ti[i]) { ins[st.top()]=0; st.pop(); } }}int main(){ while(scanf("%d %d",&n,&m)!=EOF) { if(n==0&&m==0)break; int i,j,a,b; inithead(); CL(lo,0); CL(ti,0); CL(ins,0); for(i=0;i<m;i++) { scanf("%d %d",&a,&b); addedge(a,b); } targan(1); int re=0; for(i=1;i<=n;i++) { if(lo[i]==ti[i])re++; } // cout<<re<<endl; if(re==1)printf("Yes\n"); else printf("No\n"); } return 0;}
HDU 1269 裸奔的强联通分量
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。