迷宫城堡

 

题意：很明显是直接让判断有向图是不是强连通分量。

 

1 #include 
      
        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
       
         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