글 읽기 - 1325번 반례를 구해주실 수 있으신가요??틀린 이유를 모르겠습니다.

pianissimo 5년 전 0

BFS를 이용해서 구현하였습니다. 그 이전에 계속 시간초과, 메모리초과가 났는데 그건 뜨지 않는데
틀렸습니다가 나오는 이유를 모르겠습니다. 사이클, 예시테스트케이스 등 여러 개를 넣어봤는데 거기까진 잘 나왔습니다.
반례 또는 틀린 이유를 알려주실 수 있으신가요..

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

typedef struct hac{
    short ee;    //야기되는컴퓨터
    short er;    //야기시키는컴퓨터
} HAC;
HAC net[100001] = {{0, 0}};
short visit[10001] = {0};
short queue[100001] = {0};
short result[10001] = {0};
short max = 0;
int main(void) {
	short N;
    short root;
	short M;
	short i=0;
    short front = 0;
    short rear = 0;
    short pop = 0;
	short j=1;
	//short temp;
	//int ans;
	short v1, v2;
	scanf("%hd", &N);
	scanf("%hd", &M);
	for(i=0; i<M; i++){
		scanf("%hd", &v1);
		scanf("%hd", &v2);
		net[i].ee = v1;
        net[i].er = v2;
	}
	for(root = 1; root<=N; root++){ //root는 시작컴퓨터 번호.
        front = 0;
        rear = 0;
        pop = 0;
        max = 0;
        visit[root] = root;
        for(i=0; i<M; i++){
            if(net[i].er == root){
                queue[rear] = net[i].ee;
                rear++;
                visit[net[i].ee] = root;
                max++;
            }
        }
            while(front < rear){
                pop = queue[front];
                front++;
                for(j=0; j<M; j++){
                    if(net[j].er == pop && visit[net[j].ee] != root){
                        queue[rear] = net[j].ee;
                        rear++;
                        visit[net[j].ee] = root;
                        max++;
                    }
                }
            }


      //  printf("max : %hd\n",max);
        result[root] = max;    //result[컴퓨터번호] = 각 컴퓨터시작시 해킹되는수
    }
    max = result[1];
    for(i=1; i<=N; i++){
        if(max < result[i])
            max = result[i];
    }

 //   printf("max : %hd\n",max);
    for(i=1; i<=N; i++){
        if(result[i] == max)
            printf("%hd ", i);
    }
    putchar('\n');
	return 0;
}

djm03178 5년 전 0

간선 정보가 최대 10만개인데 short로는 32767까지밖에 세지 못합니다.

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

문제

문제

출처

ICPC

1325번 반례를 구해주실 수 있으신가요??틀린 이유를 모르겠습니다.

pianissimo 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말