글 읽기 - 어떤 케이스에서 메모리 초과가 나는 걸까요

kimyongdae 3년 전 0

제 풀이는 위상정렬 처럼 차수를 세어 (위상정렬 사용했단 말은 아님)

차수가 0인 노드들에서 bfs를 돌립니다.

그렇게 방문한 노드들은 서로 관계를 알게 되니 그 개수만큼 전체 개수에서 뺴줍니다.

중복되는 노드들은 여러번 계산되지 않도록 처리해주고요.

정답은 틀렸더라도 왜 메모리초과가 나는지 궁금합니다.

예상 1) 큐와 벡터를 너무 많이 만들었다.

n이 100 m이 1000이라 최악의 상황에도 메모리 초과가 날 상황은 아니라 생각됩니다.

예상 2) 방문 처리 안해서 무한 사이클

음 이러면 시간초과로 뜨지 않나요.

그리고 대소 관계이기 때문에 사이클이 생길 수 없지 않나요!!

부탁드립니다.

#include<stdio.h>
#include<queue>
#include<vector>
using namespace std;
int n,m,deg[104],a,b,vis[104],ans[104];
vector<int> v[104];
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d %d",&a,&b);
        v[a].push_back(b);
        deg[b]++;
    }
    for(int i=1;i<=n;i++) ans[i]=n-1;
    for(int i=1;i<=n;i++){
        if(deg[i]!=0) continue;
        queue<int> q;  q.push(i);
        vector<int> check,overlab;
        while(!q.empty()){
            int now=q.front(); q.pop();
            if(vis[now]>0) overlab.push_back(now);
            vis[now]++;
            check.push_back(now);
            for(int i=0;i<v[now].size();i++)
                q.push(v[now][i]);
        }
        for(int i=0;i<check.size();i++) ans[check[i]]-=check.size()-1;
        for(int i=0;i<overlab.size();i++) ans[overlab[i]]+=overlab.size()-1;

    }
    for(int i=1;i<=n;i++)
    printf("%d\n",ans[i]);
}

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

문제

문제

출처

ICPC

어떤 케이스에서 메모리 초과가 나는 걸까요

kimyongdae 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말