글 읽기 - 왜시간초과가 날까요? 정답코드랑 크게 차이가없는데요..

qktlf789456 3년 전 0

DFS접근을했고

이미 계산된 것에 대해서 DP도 따로 만들었습니다.

A -> B 라면

B -> A 로 연결리스트를 구성하였습니다.

visited 로 순환 예외처리도 했습니다... 뭐가문제일까요?

#include <iostream>


using namespace std;

/*
ios_base::sync_with_stdio(0);
cin.tie(0);
5 4
3 1
3 2
4 3
5 3

*/

int node_size, edge_size;

struct node
{
    int to;
    struct node* link;
};

struct node* table[10001]{ 0, };

int dp[10001]{ 0, };


void insert(int a, int b)
{
    struct node* newnode = new struct node;
    newnode->to = b;
    newnode->link = table[a];
    table[a] = newnode;

}

int max_idx[10001];
int max_idx_size = 0;
int max_value = -1;

char visited[10001]{ 0, };
int dfs(int cur_node)
{
    if (visited[cur_node])
        return 0;


    if (dp[cur_node])
        return dp[cur_node];
    

    visited[cur_node] = 1;
    

    int return_value = 1;


    for (struct node* next_node = table[cur_node]; next_node; next_node = next_node->link)
    {
        return_value += dfs(next_node->to);
    }

    
    visited[cur_node] = 0;
    return (dp[cur_node] = return_value);
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);


    cin >> node_size >> edge_size;

    int a, b;
    
    for (int i = 0; i < edge_size; i++)
    {
        cin >> a >> b; //a 가 b를 신뢰한다, 즉 b가 a에 의하여 가르킴을당함

        insert(b, a);
    }

    
    int value;
    for (int i = 1; i <= node_size; i++)
    {
        value = dfs(i);
          //  cout << i << "  = " << value << "\n";
        if (max_value <= value)
        {
            if (max_value == value) //값이동일하다면 추가
            {
                max_idx[max_idx_size++] = i;
            }
            else
            {//새로운값 갱신이라면 하나만갱신
                max_idx_size = 0;
                max_idx[max_idx_size++] = i;
                max_value = value;
            }

        }
        
    }


    for (int i = 0; i < max_idx_size; i++)
        cout << max_idx[i] << " ";

   



    return 0;
}

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

문제

문제

출처

ICPC

왜시간초과가 날까요? 정답코드랑 크게 차이가없는데요..

qktlf789456 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말