글 읽기 - 시간초과 ㅠㅠㅠ....

kammat1 5년 전 0

Char을 씀으로써 일단 메모리 제한은 우회했는데 시간초과가 뜨네요.... 더 괜찮은 방법이 존재하나요?

#include <stdio.h>

int n, m;
char dfsmap[10001][10001];
int visit[10001];
int othercnt = 1;

int dfs(int number)
{
    visit[number] = 1;
    for(int i = 1; i <= n; i++)
    {
        if(dfsmap[number][i] == '1' && visit[i] == 0)
        {
            othercnt++;
            //printf("%d %d 이동\n", number, i);
            dfs(i);
        }
    }
    return othercnt;
}

int main(void)
{
    int cntarray[10001];
    int front, end;
    int cnt = 0;
    int max = 0;
    scanf("%d %d", &n, &m);
    
    for(int i = 1; i <= m; i++)
    {
        scanf("%d %d", &front, &end);
        dfsmap[end][front] = '1';
    }
    
    for(int i = 1; i <= n; i++)
    {
        for(int i = 1; i <= n; i++) visit[i] = 0;
        cnt = dfs(i);
        cntarray[i] = cnt;
        if(cnt > max) max = cnt;
        othercnt = 1;
        //printf("%d\n", cnt);
    }
    
    for(int i = 1; i <= n; i++)
    {
        if(cntarray[i] == max)
        {
            printf("%d ", i);
        }
    }

    return 0;
}

hyunynim 5년 전 0

그래프를 표현함에 있어서 인접행렬이 아닌 인접 리스트를 사용해보시는 것은 어떨까요?

인접행렬의 경우 dfs의 시간복잡도가 상당히 걸리는 것으로 알고 있습니다!

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

문제

문제

출처

ICPC

시간초과 ㅠㅠㅠ....

kammat1 5년 전 0

hyunynim 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말