迷宫城堡
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 19017 Accepted Submission(s):
8328
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结束。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include<stack>
using namespace std; #define MAXN 10010
#define MAXM 100010
stack<int>s;
int head[MAXN],dfn[MAXN], low[MAXN], belong[MAXM];
int instack[]; // instack[]为是否在栈中的标记数组
int n, m, cnt, scnt, top, tot;
struct Edge
{
int v, next;
}e[MAXM]; //边结点数组 void add(int u,int v)
{
e[++cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt; }
void init()
{
cnt = ;
scnt=; //初始化连通分量标号
memset(head, -, sizeof(head));
memset(dfn, , sizeof(dfn)); //结点搜索的次序编号数组为0，同时可以当是否访问的数组使用
while(!s.empty()) s.pop();
} void Tarjan(int v)
{
int min,t;
dfn[v]=low[v]=cnt++;
instack[v]=;
s.push(v);
for(int i=head[v];i!=-;i=e[i].next)
{
int j=e[i].v;
if(!dfn[j])//未被访问
{
Tarjan(j);
// 更新结点v所能到达的最小次数层
if(low[v]>low[j])
low[v]=low[j];
}
else if(instack[j]&&low[v]>dfn[j])
{//如果j结点在栈内,
low[v]=dfn[j];
}
}
if(dfn[v]==low[v])
{//如果节点v是强连通分量的根
scnt++;
do
{
t=s.top();
s.pop();
instack[t]=;
belong[t]=scnt;
}
while(t!=v);
}
} int main()
{
while(scanf("%d%d",&n,&m) && (n || m))
{
init();
while(m--)
{
int u,v;
scanf("%d%d", &u, &v);
add(u,v);
}
cnt=;
for(int i = ; i <= n; i++) //枚举每个结点，搜索连通分量
{
if(!dfn[i]) //未被访问
{
Tarjan(i); //则找i结点的连通分量 }
}
if(scnt == ) printf("Yes\n"); //只有一个强连通分量，说明此图各个结点都可达
else printf("No\n");
}
return ;
}
Output
对于输入的每组数据，如果任意两个房间都是相互连接的，输出"Yes"，否则输出"No"。
Sample Input
3 3
1 2
2 3
3 1
3 3
1 2
2 3
3 2
0 0
1 2
2 3
3 1
3 3
1 2
2 3
3 2
0 0
Sample Output
Yes
No
No
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include<stack>
using namespace std; #define MAXN 10010
#define MAXM 100010
stack<int>s;
int head[MAXN],dfn[MAXN], low[MAXN], belong[MAXM];
int instack[]; // instack[]为是否在栈中的标记数组
int n, m, cnt, scnt, top, tot;
struct Edge
{
int v, next;
}e[MAXM]; //边结点数组 void add(int u,int v)
{
e[++cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt; }
void init()
{
cnt = ;
scnt=; //初始化连通分量标号，次序计数器，栈顶指针为0
memset(head, -, sizeof(head));
memset(dfn, , sizeof(dfn)); //结点搜索的次序编号数组为0，同时可以当是否访问的数组使用
while(!s.empty()) s.pop();
} void Tarjan(int v)
{
int min,t;
dfn[v]=low[v]=cnt++;
instack[v]=;
s.push(v);
for(int i=head[v];i!=-;i=e[i].next)
{
int j=e[i].v;
if(!dfn[j])
{
Tarjan(j);
if(low[v]>low[j])
low[v]=low[j];
}
else if(instack[j]&&low[v]>dfn[j])
{
low[v]=dfn[j];
}
}
if(dfn[v]==low[v])
{
scnt++;
do
{
t=s.top();
s.pop();
instack[t]=;
belong[t]=scnt;
}
while(t!=v);
}
} int main()
{
while(scanf("%d%d",&n,&m) && (n || m))
{
init();
while(m--)
{
int u,v;
scanf("%d%d", &u, &v);
add(u,v);
}
cnt=;
for(int i = ; i <= n; i++) //枚举每个结点，搜索连通分量
{
if(!dfn[i]) //未被访问
{
Tarjan(i); //则找i结点的连通分量 }
}
if(scnt == ) printf("Yes\n"); //只有一个强连通分量，说明此图各个结点都可达
else printf("No\n");
}
return ;
}
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std; #define MAXN 10010
#define MAXM 100010 struct Edge
{
int v, next;
}edge[MAXM]; //边结点数组 int first[MAXN], stack[MAXN], DFN[MAXN], Low[MAXN], Belong[MAXM];
// first[]头结点数组,stack[]为栈,DFN[]为深搜次序数组，Belong[]为每个结点所对应的强连通分量标号数组
// Low[u]为u结点或者u的子树结点所能追溯到的最早栈中结点的次序号
int instack[]; // instack[]为是否在栈中的标记数组
int n, m, cnt, scnt, top, tot; void init()
{
cnt = ;
scnt = top = tot = ; //初始化连通分量标号，次序计数器，栈顶指针为0
memset(first, -, sizeof(first));
memset(DFN, , sizeof(DFN)); //结点搜索的次序编号数组为0，同时可以当是否访问的数组使用
} void read_graph(int u, int v) //构建邻接表
{
edge[tot].v = v;
edge[tot].next = first[u];
first[u] = tot++;
} void Tarjan(int v) //Tarjan算法求有向图的强连通分量
{
int min, t;
DFN[v] = Low[v] = ++tot; //cnt为时间戳
instack[v] = ; //标记在栈中
stack[top++] = v; //入栈
for(int e = first[v]; e != -; e = edge[e].next)
{ //枚举v的每一条边
int j = edge[e].v; //v所邻接的边
if(!DFN[j])
{ //未被访问
Tarjan(j); //继续向下找
if(Low[v] > Low[j]) Low[v] = Low[j]; // 更新结点v所能到达的最小次数层
}
else if(instack[j] && DFN[j] < Low[v])
{ //如果j结点在栈内,
Low[v] = DFN[j];
}
}
if(DFN[v] == Low[v])
{ //如果节点v是强连通分量的根
scnt++; //连通分量标号加1
do
{
t = stack[--top]; //退栈
instack[t] = ; //标记不在栈中
Belong[t] = scnt; //出栈结点t属于cnt标号的强连通分量
}while(t != v); //直到将v从栈中退出
}
} void solve()
{
for(int i = ; i <= n; i++) //枚举每个结点，搜索连通分量
if(!DFN[i]) //未被访问
Tarjan(i); //则找i结点的连通分量
} int main()
{
while(scanf("%d%d",&n,&m) && (n || m))
{
init();
while(m--)
{
int u, v;
scanf("%d%d", &u, &v);
read_graph(u, v);
}
solve(); //求强连通分量
if(scnt == ) printf("Yes\n"); //只有一个强连通分量，说明此图各个结点都可达
else printf("No\n");
}
return ;
}
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector> using namespace std;
vector<int>gh1[];//向量
vector<int>gh2[];
int cnt;
int vir[];
void dfs1(int n)
{
int x;
vir[n] = ;
cnt++;
for (int i = ; i<gh1[n].size(); i++)
{
x = gh1[n].at(i);
if (vir[x] == )
dfs1(x);
}
}
void dfs2(int n)
{
int x;
vir[n] = ;
cnt++;
for (int i = ; i<gh2[n].size(); i++)
{
x = gh2[n].at(i);
if (vir[x] == )
dfs2(x);
}
} int main()
{
int m, n, a, b;
while (~scanf("%d%d", &n, &m) && (m || n))
{
for (int i = ; i <= n; i++)
{
gh1[i].clear();
gh2[i].clear();
}
for (int i = ; i <= m; i++)
{
scanf("%d%d", &a, &b);
gh1[a].push_back(b);
gh2[b].push_back(a);
}
memset(vir, , sizeof(vir));
cnt = ;
dfs1();//正的走一次
if (cnt != n)
{
printf("No\n");
continue;
}
memset(vir, , sizeof(vir));
cnt = ;
dfs2();//反的走一次
if (cnt != n)
{
printf("No\n");
continue;
}
printf("Yes\n"); } return ;
}