글 읽기 - 두 코드가 왜 이렇게 시간 차이가 많이 발생하는지 이해가 되지 않습니다.

repelit 1년 전 0

dfs를 돌리는 eucfind 함수만 다르며

포인터의 사용 여부에만 차이가 있음에도 왜 이렇게 코드의 시간이 오래 걸리는지 궁금합니다.

#include<bits/stdc++.h>

using namespace std;

int n;
int arr[1010][1010];
int nxt[1010];
int deg[1010];
///////////////////////////////////////////////////
//AC 1: 640ms
void eucfnd(int st)
{
    for(int &i=nxt[st]; i<=n; i++)
    {
        while(arr[st][i])
        {
            arr[st][i]--;
            arr[i][st]--;
            eucfnd(i);
        }
    }

    cout<<st<<' ';
}
////////////////////////////////////////////////////
//AC 2: 2384 ms
void eucfnd(int st)
{
    for(int i=nxt[st]; i<=n; i++)
    {
        while(nxt[st]<=n and arr[st][nxt[st]])
        {
            arr[st][nxt[st]]--;
            arr[nxt[st]][st]--;
            eucfnd(nxt[st]);
        }
        nxt[st]++;
    }
    cout<<st<<' ';
}
//////////////////////////////////////////////////////

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>n;

    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
        {
            cin>>arr[i][j];
            deg[i]+=arr[i][j];
        }

    bool impo=false;
    for(int i=1; i<=n; i++)
        if(deg[i]%2)
        {
            impo=true;
            break;
        }

    if(impo)
        cout<<-1;

    else
    {
        for(int i=1; i<=n; i++)
            nxt[i]=1;
        eucfnd(1);
    }
}

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

문제

문제

출처

ICPC

두 코드가 왜 이렇게 시간 차이가 많이 발생하는지 이해가 되지 않습니다.

repelit 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말