HDU 1269 迷宫城堡

迷宫城堡

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 5646 Accepted Submission(s): 2502

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

Author

Gardon

Source

HDU 2006-4 Programming Contest

Recommend

lxj | We have carefully selected several similar problems for you: 1142 1217 1068 1116 1150

思路：第一次照着模板写Tarjan，还因为head数组没有初始化，wa了无数次

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
int N,M,m;
int a,b;
int the_last_sum;
int dfn[11000];
int low[11000];
int temp[11000];
int stack[110000];
int head[11000];
struct Node
{
    int t,next;
}Edge[110000];
int tarbfs(int k,int lay,int &scc_num)
{
    temp[k] = 1;
    low[k] = lay;
    dfn[k] = lay;
    stack[++ m] = k;
    for(int i = head[k];i != 0;i = Edge[i].next)
    {
        if(temp[Edge[i].t] == 0)
        {
            tarbfs(Edge[i].t,++ lay,scc_num);
        }
        if(temp[Edge[i].t] == 1)
           low[k] = min(low[k],low[Edge[i].t]);
    }
    if(dfn[k] == low[k])
    {
        scc_num ++;
        do
        {
            low[stack[m]] = scc_num;
            temp[stack[m]] = 2;
        }while(stack[m --] != k);
    }
    return 0;
}
int tarjan(int n)
{
    int scc_num = 0,lay = 1;
    m = 0;
    memset(temp,0,sizeof(temp));
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    for(int i = 1;i <= n;i ++)
    {
        if(temp[i] == 0)
        {
            tarbfs(i,lay,scc_num);
        }
    }
    return scc_num;
}
int main()
{
    while(~scanf("%d%d",&N,&M))
    {
        if(N == 0 && M == 0)
            break ;
        memset(Edge,0,sizeof(Edge));
        memset(head,0,sizeof(head));
        for(int i = 1;i <= M;i ++)
        {
            scanf("%d%d",&a,&b);
            Edge[i].t = b;
            Edge[i].next = head[a];
            head[a] = i;
        }
        the_last_sum = tarjan(N);
        if(the_last_sum > 1)
            printf("No
");
        else
            printf("Yes
");
    }
    return 0;
}