迷宫城堡
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 10409 Accepted Submission(s): 4674
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
3 3 1 2 2 3 3 1 3 3 1 2 2 3 3 2 0 0
Sample Output
Yes No
题解：
强联通问题，targin算法，或者dfs做，建图也可以用邻接表，或者vector；
方法一dfs：
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 #define MAX(x,y)(x>y?x:y) 8 #define MIN(x,y)(x
方法二：targin算法：
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #define mem(x,y) memset(x,y,sizeof(x)) 9 using namespace std;10 const int INF=0x3f3f3f3f;11 const int MAXN=10010;12 //#define LOCAL13 vector vec[MAXN];14 stack S;15 int dfn[MAXN],low[MAXN],Instack[MAXN];16 int scc,dfs_block;17 void targin(int u,int fa){18 dfn[u]=low[u]=++dfs_block;19 S.push(u);20 Instack[u]=1;21 for(int i=0;i
邻接表建图又写了一遍，邻接表都不太熟练了：
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 const int INF=0x3f3f3f3f;10 //#define LOCAL11 #define mem(x,y) memset(x,y,sizeof(x))12 const int MAXN=10010;13 const int MAXM=100010;//<<1;14 int head[MAXM],low[MAXN],dfn[MAXN],Instack[MAXN];15 int edgnum,dfs_block,lcc;16 stack S;17 struct Edge{18 int from,to,next;19 };20 Edge edg[MAXM];21 void add(int u,int v){22 Edge E={u,v,head[u]};23 edg[edgnum]=E;24 head[u]=edgnum++;//**25 }26 void targin(int u,int fa){27 low[u]=dfn[u]=++dfs_block;28 S.push(u);29 Instack[u]=1;30 for(int i=head[u];i!=-1;i=edg[i].next){ //**31 int v=edg[i].to;32 if(!dfn[v]){33 targin(v,u);34 low[u]=min(low[v],low[u]);35 }36 else if(Instack[v]){37 low[u]=min(low[u],dfn[v]);38 }39 }40 if(low[u]==dfn[u]){41 lcc++;42 while(1){43 int v=S.top();44 S.pop();45 Instack[v]=0;46 if(u==v)break;47 }48 }49 }50 int main(){51 #ifdef LOCAL52 freopen("data.in","r",stdin);53 freopen("data.out","w",stdout);54 #endif55 int N,M;56 while(~scanf("%d%d",&N,&M),N|M){57 mem(head,-1);mem(dfn,0);mem(low,0);mem(Instack,0);58 edgnum=dfs_block=lcc=0;59 while(!S.empty())S.pop();60 int a,b;61 while(M--){62 scanf("%d%d",&a,&b);63 add(a,b);64 }65 for(int i=1;i<=N;i++){66 if(dfn[i])continue;67 targin(i,-1);68 }69 if(lcc==1)puts("Yes");70 else puts("No");71 }72 return 0;73 }