【HDU 1269】迷宫城堡 强联通模板 要求全图只有一个强联通分量 成立则Yes否则No
可能有一些独立的点 所以要从头到尾遍历 为此献了几个WA 节哀
代码如下
;vector <int> head[11111];stack <int> s;int dfn[11111],low[11111];int vis[11111];int f,t,n,m;void Init(){int i;for(i = 1; i <= n; ++i)head[i].clear();t = f = 0;memset(vis,0,sizeof(vis));while(!s.empty()) s.pop();}void Tarjan(int u){dfn[u] = low[u] = t++;int i,v;s.push(u);vis[u] = -1;for(i = 0; i < head[u].size(); ++i){v = head[u][i];if(!vis[v]){Tarjan(v);if(f == 2) return;low[u] = min(low[v],low[u]);}else if(vis[v] == -1){low[u] = min(low[u],dfn[v]);}}if(dfn[u] == low[u]){if(f){f = 2;return;}f = 1;while(s.top() != u){vis[s.top()] = 1;s.pop();}vis[s.top()] = 1;s.pop();}}int main(){int i,u,v;while(~scanf(“%d %d”,&n,&m) && (m+n)){Init();for(i = 0; i < m; ++i){scanf(“%d %d”,&u,&v);head[u].push_back(v);}for(i = 1; i <= n; ++i)if(!vis[i])Tarjan(i);if(f == 1) printf(“Yes\n”);else printf(“No\n”);}return 0;}
，莫找借口失败，只找理由成功。(不为失败找理由，要为成功找方法)
