hdu 1269 迷宫城堡（tarjan强连通）

hdu 1269 迷宫城堡

http://acm.hdu.edu.cn/showproblem.php?pid=1269

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

tarjan强连通：

强连通问题，选用tarjan算法，如果单纯的判断，并查集也可以考虑！但，tarjan算法的作用不止可以判断是否连通，还可以求出各个子树！

#include<iostream>
#include<vector>
#include<stack>
using namespace std;
#define MAX 10001
vector<int> v[MAX];
int DFN[MAX],low[MAX],index,count;
bool instack[MAX];
stack<int> s;
int min(int a,int b){return a<b?a:b;}
void tarjan(int u)
{
 DFN[u]=low[u]=++index;
 instack[u]=true;
 s.push(u);
 int i,k;
 for(i=0;i<v[u].size();i++)
 {
  k=v[u][i];
  if(!DFN[k])
  {
   tarjan(k);
   low[u]=min(low[u],low[k]);
  }
  else if(instack[k])
   low[u]=min(low[u],DFN[k]);
 }
 if(low[u]==DFN[u])
 {
  count++;
  do
  {
   k=s.top();
   s.pop();
   instack[k]=false;
  }
  while(u!=k);
 }
}
int na[MAX],nb[MAX];
int main()
{
 int n,m;
 while(~scanf("%d%d",&n,&m),n+m)
 {
  int i,a,b;
  for(i=1;i<=n;i++)
   v[i].clear();
  memset(na,0,sizeof(na));
  memset(nb,0,sizeof(nb));
  for(i=1;i<=m;i++)
  {
   scanf("%d%d",&a,&b);
   v[a].push_back(b);
  }
  memset(DFN,0,sizeof(DFN));
  memset(instack,0,sizeof(instack));
  index=0;
  int num=0;
  count=0;
  for(i=1;i<=n;i++)
   if(!DFN[i])
    tarjan(i);
  if(count>1)
   puts("No");
  else
   puts("Yes");
 }
 return 0;
}