题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1269
思路分析:该问题要求判断是否每两个房间都可以相互到达,即求该有向图中的所有点是否只构成一个强连通图分量,使用Tarjan算法即可求解;
代码如下:
#include <stack>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std; const int MAX_N = + ;
vector<int> G[MAX_N];
stack<int> S;
int pre[MAX_N], lowlink[MAX_N], scc_no[MAX_N];
int dfs_clock, scc_cnt; inline int Min(int a, int b) { return a < b ? a : b; }
void Dfs(int u)
{
pre[u] = lowlink[u] = ++dfs_clock;
S.push(u); for (int i = ; i < G[u].size(); ++i)
{
int v = G[u][i]; if (!pre[v])
{
Dfs(v);
lowlink[u] = Min(lowlink[u], lowlink[v]);
} else if (!scc_no[v])
lowlink[u] = Min(lowlink[u], lowlink[v]);
}
if (lowlink[u] == pre[u])
{
scc_cnt++;
for (;;)
{
int x = S.top();
S.pop();
scc_no[x] = scc_cnt;
if (x == u) break;
}
}
} inline void FindScc(int n)
{
dfs_clock = scc_cnt = ;
memset(pre, , sizeof(pre));
memset(lowlink, , sizeof(lowlink));
memset(scc_no, , sizeof(scc_no));
for (int i = ; i <= n; ++i)
if (!pre[i]) Dfs(i);
} int main()
{
int ver_num, road_num; while (scanf("%d %d", &ver_num, &road_num) != EOF
&& (ver_num + road_num))
{
int ver_1, ver_2; for (int i = ; i < MAX_N; ++i)
G[i].clear( );
for (int i = ; i < road_num; ++i)
{
scanf("%d %d", &ver_1, &ver_2);
G[ver_1].push_back(ver_2);
}
FindScc(ver_num);
while (!S.empty( ))
S.pop( );
if (scc_cnt > )
printf("No\n");
else
printf("Yes\n");
}
return ;
}