首页 > 代码库 > 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 裸奔的强联通分量