1269f 迷宫城堡.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

/*
1269f 迷宫城堡
Time Limit : 1000 ms  Memory Limit : 32768 K  Output Limit : 256 K

GUN C++
*/
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
#define MAX 10000

queue<int> Q1;
vector<vector<int> > v;
int iCount;
bool bCircle;
bool Mark[MAX];
int Circle[MAX];

void Search_Circle(int iStart)
{
    if(bCircle)
        return;
    if(Mark[iStart])
        return;
    if(Circle[iStart] == 1)
    {
        bCircle = true;
        return;
    }

    Mark[iStart] = true;

    int i;
    for(i = 0; i < v[iStart].size(); i++)
    {
        Search_Circle(v[iStart][i]);
    }
    if(bCircle == true)
    {
        Circle[iStart] = 1;
        Q1.push(iStart);
        iCount++;
    }
}


int main()
{
    int iRoom_Num, iPath_Num;
    int i;
    int iStart, iFinish, iBuffer;

    v.resize(MAX + 1);
    while(scanf("%d%d", &iRoom_Num, &iPath_Num) != EOF)
    {
        if(iRoom_Num == 0 && iPath_Num == 0)
            break;

        for(i = 0; i < MAX + 1; i++)
            v[i].clear();

        for(i = 0; i < iPath_Num; i++)
        {
            scanf("%d%d", &iStart, &iFinish);
            v[iStart].push_back(iFinish);
        }

        iCount = 1;
        Circle[iStart] = 1;
        bCircle = false;

        for(i = 0; i < v[iStart].size(); i++)
            Q1.push(v[iStart][i]);

        while(!Q1.empty())
        {
            iBuffer = Q1.front();
            if(iCount == iRoom_Num)
                break;
            Search_Circle(iBuffer);
            bCircle = false;
            Q1.pop();
        }
        while(!Q1.empty())
            Q1.pop();

        if(iCount == iRoom_Num)
            printf("Yes\n");
        else
            printf("No\n");

        memset(Circle, 0, sizeof(Circle));
        memset(Mark, false, sizeof(Mark));
    }
    return 0;
}