글 읽기 - 반례가 있을까요?

dlguswo333 4년 전 0

일단 제 알고리즘의 방식은,

1. 각 변호사들이 신뢰하는 변호사들의 수를 저장해준다.

2. 같은 변호사들로 이루어진 쌍, 그러니까 양방향 edge가 등장하면 따로 루프임을 명시해준다.

3. 만약 신뢰하는 변호사의 수가 0인 변호사가 있으면 NO.

4. 그 다음 루프 관계를 가진 두 변호사가 서로 말고 신뢰하는 변호사가 없으면 NO. (54번 줄)

5. 그 다음은 YES.

정답 알고리즘이 YES인 걸 제 알고리즘이 NO 할 리는 없어 보이고, NO인 걸 YES로 출력하는 걸로 예상되는데, 그걸 보여주는 반례가 있을까요?

#include <stdio.h>
#include <stdlib.h>
typedef struct Defender_{
    struct Defender_ *next;
    int ind;
    int loop;
} Defender;
void init_defender(int ind, Defender **defender){
    *defender=(Defender *)malloc(sizeof(Defender));
    (*defender)->ind=ind;
    (*defender)->loop=0;
    (*defender)->next=NULL;
}
int main(void){
    int N, M, i, a, b, *num_defender, keep_going=1;
    Defender **defender, *cursor, *prev;
    scanf("%d %d", &N, &M);
    num_defender=(int *)calloc(N, sizeof(int));
    defender=(Defender **)calloc(N, sizeof(Defender *));
    for(i=0;i<M;i++){
        scanf("%d %d", &a, &b);
        num_defender[b-1]++;
        if(a>b){
            int tmp=a;
            a=b;
            b=tmp;
        }
        if((cursor=defender[b-1])==NULL){
            init_defender(a-1, &defender[b-1]);
            continue;
        }
        do{
            if(cursor->ind==a-1){
                cursor->loop=1;
                break;
            }
            prev=cursor;
            cursor=cursor->next;
        }while(cursor!=NULL);
        if(cursor==NULL){
            Defender *new;
            init_defender(a-1, &new);
            prev->next=new; 
        }
    }
    for(i=0;keep_going && i<N;i++){
        printf("%d: %d\n", i, num_defender[i]);
        if(num_defender[i]==0){
            printf("NO");
            keep_going=0;
        }
        cursor=defender[i];
        while(cursor!=NULL){
            if(cursor->loop && num_defender[i]==1 && num_defender[cursor->ind]==1){
                printf("NO");
                keep_going=0;
                break;
            }
            cursor=cursor->next;
        }
    }
    if(keep_going)
        printf("YES");
    free(num_defender);
    for(i=0;i<N;i++){
        prev=defender[i];
        while(prev!=NULL){
            cursor=prev->next;
            free(prev);
            prev=cursor;
        }
    }
    free(defender);
    return 0;
}

ha_ram 4년 전 2

반례입니다.

3 4
1 2
2 1
1 3
3 1

답 : NO

dlguswo333 4년 전 1

감사합니다! 답변 덕분에 이해됐어요!

서로 신뢰하는 관계의 변호사 간 두 edge를 이거 하나 저거 하나 없애보면서 DFS로 구상해볼게요!

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

문제

문제

출처

ICPC

반례가 있을까요?

dlguswo333 4년 전 0

ha_ram 4년 전 2

dlguswo333 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말