迷宫城堡

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

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

整个图是一个连通块就yes,所以求连通块的个数

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <algorithm>

#include <stack>

#include <vector>

using namespace std;

const int Max = ;

vector<int> gra[Max];

stack<int> sta;

int dfn[Max], low[Max];

int Instack[Max]; // 在不在栈中

vector<int> Component[Max]; //为每个连通块开一个数组存每个连通块的点

int InComponent[Max]; // 在哪个连通块中

int index, ComponentNumber; // index就是访问时间，componentNumber就是连通块数量

int n, m;

int Min(int x, int y)

{

    return x > y ? y : x;

}

void init()

{

    index = ComponentNumber = ;

    memset(dfn, , sizeof(dfn));

    memset(low, , sizeof(low));

    memset(Instack, , sizeof(Instack));

    for(int i = ; i <= n; i++)

    {

        gra[i].clear();

        Component[i].clear();

    }

    while(!sta.empty())

        sta.pop();

}

void input()

{

    int a, b;

    for(int i = ; i <= m; i++)

    {

        scanf("%d%d", &a, &b);

        gra[a].push_back(b);

    }

}

void tarjan(int u)

{

    low[u] =  dfn[u] = ++index;

    sta.push(u);

    Instack[u] = ;  // u进栈

    int len = gra[u].size();

    for(int i = ; i < len; i++)

    {

        int t = gra[u][i];

        if(!Instack[t])  // 也就是没访问的意思

        {

            tarjan(t);

            low[u] = Min(low[u], low[t]);

        }

        else if(Instack[t] == )

        {

            low[u] = Min(low[u], dfn[t]);

        }

    }

    if(dfn[u] == low[u]) // 相等的话找到一个连通块

    {

        ++ComponentNumber;

        while(!sta.empty())

        {

            int x = sta.top();

            sta.pop();

            Instack[x] = ;

            Component[ComponentNumber].push_back(x); //x属于componentNumber连通块

            InComponent[x] = ComponentNumber;

            if(x == u)

                break;

        }

    }

}

void solve()

{

    for(int i = ; i <= n; i++)

    {

        if(!dfn[i])

            tarjan(i);

    }

    if(ComponentNumber > )

        printf("No\n");

    else

        printf("Yes\n");

}

int main()

{

    while(scanf("%d%d", &n, &m) != EOF)

    {

        if(n ==  && m == )

            break;

        init();

        input();

        solve();

    }

}

巴特西

HD1269迷宫城堡(有向图 && 划分连通块）

迷宫城堡

最新文章

热门文章