hdu 1269 迷宫城堡（强连通 tarjan ） - c++编程基础

TOP

hdu 1269 迷宫城堡（强连通 tarjan ）

2015-07-20 17:14:22 来源: 作者: 【大中小】浏览:3次

Problem Description 为了训练小希的方向感，Gardon建立了一座大城堡，里面有N个房间(N<=10000)和M条通道(M<=100000)，每个通道都是单向的，就是说若称某通道连通了A房间和B房间，只说明可以通过这个通道由A房间到达B房间，但并不说明通过它可以由B房间到达A房间。Gardon需要请你写个程序确认一下是否任意两个房间都是相互连通的，即：对于任意的i和j，至少存在一条路径可以从房间i到房间j，也存在一条路径可以从房间j到房间i。

Input 输入包含多组数据，输入的第一行有两个数：N和M，接下来的M行每行有两个数a和b，表示了一条通道可以从A房间来到B房间。文件最后以两个0结束。

Output 对于输入的每组数据，如果任意两个房间都是相互连接的，输出"Yes"，否则输出"No"。

Sample Input

Sample Output

Yes
No

强联通分支为一就是强连通图

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
            #define L(x) (x<<1) #define R(x) (x<<1|1) #define MID(x,y) ((x+y)>>1) #define eps 1e-8 typedef __int64 ll; #define FRE(i,a,b) for(i = a; i <= b; i++) #define mem(t, v) memset ((t) , v, sizeof(t)) #define sf(n) scanf("%d", &n) #define sff(a,b) scanf("%d %d", &a, &b) #define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c) #define pf printf #define bug pf("Hi\n") using namespace std; #define N 10005 int head[N],low[N],time[N],e_num,tim_num; int n,m,ans,instack[N]; struct stud{ int to,next; }e[N*10]; stack
            
             q; inline void add(int u,int v) { e[e_num].to=v; e[e_num].next=head[u]; head[u]=e_num++; } void tarjan(int x) { int i,j; q.push(x); instack[x]=1; time[x]=low[x]=++tim_num; for(i=head[x];i!=-1;i=e[i].next) { int to=e[i].to; if(time[to]==0) { tarjan(to); if(low[x]>low[to]) low[x]=low[to]; } else if(instack[to]&&low[x]>time[to]) low[x]=time[to]; } if(low[x]==time[x]) { ans++; do{ j=q.top(); q.pop(); instack[j]=0; }while(j!=x); } } void solve() { int i,j; mem(time,0); mem(instack,0); ans=tim_num=0; for(i=1;i<=n;i++) if(time[i]==0) tarjan(i); if(ans==1) printf("Yes\n"); else printf("No\n"); } int main() { int i,j; while(scanf("%d%d",&n,&m),n+m) { int u,v; e_num=0; mem(head,-1); while(m--) { sff(u,v); add(u,v); } solve(); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：门面模式(Facade)	下一篇：poj Popular Cows（tarjan +缩点）

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: