迷宫城堡
题意：很明显是直接让判断有向图是不是强连通分量。
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxv=10010; 4 const int maxe=100010; 5 int n,m; 6 struct Edge{ 7 int v,nex; 8 }e[maxe<<1]; 9 int head[maxv]; 10 int cnt=0; 11 void init(){ 12 memset(head,-1,sizeof(head)); 13 cnt=0; 14 } 15 void add(int u,int v){ 16 e[cnt].v=v; 17 e[cnt].nex=head[u]; 18 head[u]=cnt++; 19 } 20 int pre[maxv],low[maxv],sccno[maxv],dfsk,scc_cnt; 21 stack<int> s; 22 23 void dfs(int u){ 24 pre[u]=low[u]=++dfsk; 25 s.push(u); 26 for(int i=head[u];i!=-1;i=e[i].nex){ 27 int v=e[i].v; 28 if(!pre[v]){ 29 dfs(v); 30 low[u]=min(low[u],low[v]); 31 } 32 else if(!sccno[v]) //还在栈里！ 33 low[u]=min(low[u],low[v]); 34 } 35 if(pre[u]==low[u]){ 36 scc_cnt++; 37 for(;;){ 38 int x=s.top(); 39 s.pop(); 40 sccno[x]=scc_cnt; 41 if(x==u) break; 42 } 43 } 44 } 45 void find_scc(int n){ 46 memset(pre,0,sizeof(pre)); 47 memset(low,0,sizeof(low)); 48 memset(sccno,0,sizeof(sccno)); 49 dfsk=scc_cnt=0; 50 for(int i=0;i<n;i++) if(!pre[i]) dfs(i); 51 } 52 int main(){ 53 while(scanf("%d%d",&n,&m)&&(n||m)){ 54 init(); 55 int u,v; 56 for(int i=0;i<m;i++){ 57 scanf("%d%d",&u,&v); 58 u--;v--; 59 add(u,v); 60 } 61 find_scc(n); 62 if(scc_cnt==1) puts("Yes"); 63 else puts("No"); 64 } 65 return 0; 66 }