글 읽기 - (BFS) 틀렸습니다라고 뜨는데 반례를 못찾겠습니다..

qefoi 1년 전 0

문제에 나온 예제는 맞게 나오는데 반례를 못찾겠습니다..

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

typedef struct{
    int x;
    int y;
}Tree;

int queue[1000001];
Tree arr[100001]; 
int m[100001]; //부모 노드의 번호를 저장
int visited[100001]; //중복 방지

int compare(const void* a, const void* b){
    Tree x=*(Tree*)a;
    Tree y=*(Tree*)b;
    if(x.x>y.x) return 1;
    else if(x.x<y.x) return -1;
    else{
        if(x.y>y.y) return 1;
        else return -1;
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n-1;i++){
        int x,y;
        scanf("%d %d",&x,&y);
        if(x>y){   
            arr[i].y=x;
            arr[i].x=y;
        }
        else{
            arr[i].x=x;
            arr[i].y=y;
        }
    }
    qsort(arr,n-1,sizeof(arr[0]),compare); //예제2와 같이 정렬하기 위해 사용
    int front=0,rear=0;
    int idx=0;
    queue[rear++]=1;
    visited[1]=1;
    while(front<rear){
        int pop=queue[front];
        int left=0,right=n-2;
        while(left<=right){  //시간초과를 막기 위해 이진탐색 사용, pop과 같은 x와 y값을 각각 탐색하여 while문을 2번 사용
            int mid=(left+right)/2;
            if(arr[mid].x>pop) right=mid-1;
            else if(arr[mid].x<pop) left=mid+1;
            else{  //temp를 사용하여 mid를 기준으로 pop과 같은 값을 찾음
                int temp=mid;
                while(arr[temp].x==pop){ //mid보다 작거나 같은 index 탐색
                    if(!visited[arr[temp].y]){
                        m[arr[temp].y]=arr[temp].x;
                        queue[rear++]=arr[temp].y;
                        visited[arr[temp].y]=1;
                    }
                    temp--;
                    if(temp<0) break;
                }
                temp=mid+1;
                while(arr[temp].x==pop){ //mid보다 큰 index 탐색
                    if(!visited[arr[temp].y]){
                        m[arr[temp].y]=arr[temp].x;
                        queue[rear++]=arr[temp].y;
                        visited[arr[temp].y]=1;
                    }
                    temp++;
                    if(temp>n-2) break;
                }
                break;
             }
        }
        left=0,right=n-2;
        while(left<=right){ //y에 대해 위와 같이 한번 더 진행
            int mid=(left+right)/2;
            if(arr[mid].y>pop) right=mid-1;
            else if(arr[mid].y<pop) left=mid+1;
            else{
                int temp=mid;
                while(arr[temp].y==pop){
                    if(!visited[arr[temp].x]){
                        m[arr[temp].x]=arr[temp].y;
                        queue[rear++]=arr[temp].x;
                        visited[arr[temp].x]=1;
                    }
                    temp--;
                    if(temp<0) break;
                }
                temp=mid+1;
                while(arr[temp].y==pop){
                    if(!visited[arr[temp].x]){
                        m[arr[temp].x]=arr[temp].y;
                        queue[rear++]=arr[temp].x;
                        visited[arr[temp].x]=1;
                    }
                    temp++;
                    if(temp>n-2) break;
                }
                break;
            }            
        }
        front++;
    }
    for(int i=2;i<=n;i++) printf("%d\n",m[i]); //부모 노드 출력
    return 0;
}

pill27211 1년 전 2

반례입니다.

Input)

10
1 3
5 4
3 2
2 7
5 7
9 10
5 10
6 8
1 6

Output)

0
1
0
0
1
0
6
0
0

Answer)

3
1
5
7
1
2
6
10
5

qefoi 1년 전 0

감사합니다 덕분에 풀었습니다

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

문제

문제

출처

ICPC

(BFS) 틀렸습니다라고 뜨는데 반례를 못찾겠습니다..

qefoi 1년 전 0

pill27211 1년 전 2

qefoi 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말