题解 hdu 1269 迷宫城堡-526互联

找点图论练习题写，发现hdu又寄了，那就发到blog里吧。

思路：tarjan缩点判断DAG中点数是否为1。若是，则该图为强连通图。

//produced by miya555
//stupid mistakes:多测记得清空
//ideas:tarjan模板
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int n,m,low[N],ne[N],h[N],idx,top;
int timestamp,dfn[N],st[N],ins[N],cnt,now,vis[N],e[N];
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void tarjan(int u){
    low[u]=dfn[u]=++timestamp;
    st[++top]=u;
    ins[u] = 1;
    for(int i=h[u];i;i=ne[i]){
        int j=e[i];
        if(!dfn[j]){
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }else if(ins[j]){
            low[u]=min(low[u],dfn[j]);
        }
    }
    if(low[u]==dfn[u]){
        cnt++;
        while(1) {
            int now = st[top];
            top--;
            vis[now]=0;
            if(now == u) break;
        }
    }
}
int a,b;
int main(){
    while(~scanf("%d%d",&n,&m)){
    //cin>>n>>m;    
    if(n == 0 && m == 0) break;
    memset(h,0,sizeof h);
    memset(vis,0,sizeof vis);
    memset(st,0,sizeof st);
    for(int i = 1; i<=n; i++) dfn[i] = low[i] = 0;
    for(int i = 1; i<=m; i++) {
            cin>>a>>b;
            add(a,b);
        }
        for(int i = 1; i<=n; i++) {
            if(dfn[i] == 0) tarjan(i);
        }
        if(cnt == 1) puts("yes");
        else puts("no");
    }
    return 0;
}

题解