글 읽기 - C++ BFS 시간 초과

phoenixrafael 2년 전 0

아래 코드에서 자꾸 시간 초과가 뜨는데... 어디서 왜 뜨는지 모르겠습니다 ㅠㅠ

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;

#define ARR 500000

int n;
int m;
int x;
int M[ARR][2];
int mx;
int mn;

int BFS(){
    std::queue<int> MXQ;
    std::queue<int> MNQ;
    int mxb;
    int mnb;
    bool MXV[ARR];
    bool MNV[ARR];

    for(int i=0; i<n; i++){
        MXV[ARR] = false;
        MNV[ARR] = false;
    }

    MXQ.push(x);
    MNQ.push(x);
    for(;;){
        if(!MXQ.empty()){
            mxb = MXQ.front();
            MXQ.pop();
            for(int i=0; i<m; i++){
                if(!MXV[M[i][0]] && M[i][1] == mxb){
                    mx += 1;
                    MXV[M[i][0]] = true;
                    MXQ.push(M[i][0]);
                }
            }
        }
        if(!MNQ.empty()){
            mnb = MNQ.front();
            MNQ.pop();
            for(int i=0; i<m; i++){
                if(!MNV[M[i][1]] && M[i][0] == mnb){
                    mn += 1;
                    MNV[M[i][1]] = true;
                    MNQ.push(M[i][1]);
                }
            }
        }
        if(MXQ.empty() && MNQ.empty()){
            return 0;
        }
    }
}

int main()
{
    mx = 0;
    mn = 0;
    scanf("%d %d %d", &n, &m, &x);
    for(int i=0; i<m; i++){
        scanf("%d %d", &M[i][0], &M[i][1]);
    }
    BFS();
    printf("%d %d", mx+1, n-mn);
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

C++ BFS 시간 초과

phoenixrafael 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말