글 읽기 - 이문제 c언어 링크드 리스트와 일반적 DFS로 풀면 시간초과가 나오나요?

cdt416z 4년 전 0

노드의 개수가 많아서 링크드 리스트를 선택했는데

일반적인 DFS로 짜니 시간초과가 나옵니다

여기서 더 최적화를 할 수 있을까요? 아니면 이 방법으로는 무조건 시간초과가 나올까요??

답변 부탁드립니다!

#include <stdio.h>
#include <stdlib.h>

typedef struct NODE *nodePointer;
typedef struct NODE{
    int go;
    nodePointer next;
}NODE;
nodePointer node[10001];

int visit[10001];
int hacking[10001] = { 0 };
int N, M;

void DFS(int num, int here){
	nodePointer header = node[here];
    while(header){
        if(visit[header->go] == 0){
            visit[header->go] = 1;
            hacking[num]++;
            DFS(num, header->go);
        }
        header = header->next;
    }
}

int main(){
    scanf("%d %d", &N, &M);
    nodePointer temp;
    for(int i = 0; i < M; i++){
        temp = (nodePointer)malloc(sizeof(NODE));
        int A, B;
        scanf("%d %d", &A, &B);
        temp->go = A;
        temp->next = node[B];
        node[B] = temp;
    }
    int max = -1;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            visit[j] = 0;
        }
        if(node[i]){
            visit[i] = 1;
            hacking[i]++;
            DFS(i, i);
        }
        if(hacking[i] > max){
            max = hacking[i];
        }
    }
    for(int i = 1; i <= N; i++){
       	if(hacking[i] == max){
       		printf("%d ", i);
    	}
    }
    return 0;
}

cdt416z 4년 전 0

c++에서의 백터를 사용한 코드와 일치하지만.. 시간초과가 나네요

rlawnddnjs12 2년 전 0

c언어 공부하고 있어서 이 문제를 c언어로 짜고 있는데 아직 해결을 못했습니다. 혹시 해결하셨다면 코드 좀 부탁드려도 될까요...!

다른 곳에서 c 자료를 찾아보려고 해도 c는 없고 다 c++의 벡터만 사용하셔서 참고할 자료가 없습니다 부탁드릴게요 ㅜㅜ

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

문제

문제

출처

ICPC

이문제 c언어 링크드 리스트와 일반적 DFS로 풀면 시간초과가 나오나요?

cdt416z 4년 전 0

cdt416z 4년 전 0

rlawnddnjs12 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말