글 읽기 - 푸는 방식의 문제인지 확인해주세요

snujoon 5년 전 0

제가 생각하는 이 문제의 핵심은

루트가 2개인가
2개를 받는것이 있는지 없는지 입니다.

그래서 구조체에 받는것과 주는것을 넣어주고 최대크기만큼 구조체를 형성한뒤에 입력받는 숫자에 따른 구조체에 수치를 대입해서 비교하려고했습니다.

어지간한 예제는 다 통과했는데 왜 아예 5%체점도 못뚫고 바로 틀렸다고 하는지 모르겠습니다...

도와주십시요

트리라 진짜 트리로 풀었는지를 확인하는건가요?

#include <iostream>
using namespace std;

typedef struct
{
    int number_of_send = 0;
    int number_of_receive = 0;
}root;

int main()
{
    bool store[100001];
    int test_count = 1;
    while(1)
    {
        int number_of_input_count = 0;
        int a, b;
        root *r = new root[100001];
        //입력부
        while(1)
        {
            cin >> a;
            cin >> b;
            if(a==-1 && b==-1)
                break;
            if(a==0 && b == 0)
                break;
            r[a].number_of_send++;
            r[b].number_of_receive++;
            number_of_input_count++;
        }
        //루트가 2개인지 확인하자
        int number_of_root_check = 0;
        for(int i=0;i<100001;i++)
        {
            if(r[i].number_of_send!=0&&r[i].number_of_receive==0)
                number_of_root_check++;
        }
        //2개를 받는것이 있는지 확인하자
        int number_of_double_receive = 0;
        for(int i=0;i<100001;i++)
        {
            if(r[i].number_of_receive>1)
                number_of_double_receive++;
        }
        if(number_of_input_count==0&&a!=0&&b!=0)
        {
            test_count--;
            break;
        }
        if(number_of_input_count==0&&a==0&&b==0)
        {
            test_count--;
        }
        else if(number_of_root_check==1 && number_of_double_receive==0)
        {
            //store[test_count] = true;
            printf("Case %d is a tree.\n",test_count);
        }
        else if(number_of_root_check!=1 && number_of_double_receive==0)
        {
            //store[test_count] = false;
            printf("Case %d is not a tree.\n",test_count);
        }
        else if(number_of_root_check==1 && number_of_double_receive!=0)
        {
            //store[test_count] = false;
            printf("Case %d is not a tree.\n",test_count);
        }
        else if(number_of_root_check!=1 && number_of_double_receive!=0)
        {
            //store[test_count] = false;
            printf("Case %d is not a tree.\n",test_count);
        }
        test_count++;
            //동적할당 해제
            free(r);
            if(a==-1 && b==-1)
                break;
        }//여기가 전체 while문 끝나는 자리
    /*
    //혹시 출력 이상일경우
    for(int i=1;i<test_count+1;i++)
    {
        if(store[i]==true)
        {
            printf("Case %d is a tree.\n",i);
        }
        else if(store[i]==false)
        {
            printf("Case %d is not a tree.\n",i);
        }
    }*/
}

adh0463 5년 전 1

'루트 노드를 제외한 모든 노드는 반드시 단 하나의 들어오는 간선이 존재한다' 문구에 힌트가 있습니다.

yukino 5년 전 3

트리를 만족하는 자료 구조는 비어 있거나(노드의 개수가 0개), 노드의 개수가 1개 이상이고...

input
0 0
-1 -1
    
output
Case 1 is a tree.

snujoon 5년 전 3

여러분 사랑합니다 이 문제에 도움을 주신 여러분들은 하시는 모든일마다 다 형통하시리라 믿습니다 래제다레ㅐㅈ맏레ㅐ맞데램자데해ㅓㅈㅁㄷ해ㅓ에래헌ㅇ러해

0 0 이 트리 성립조건이었다니.... 흙흙

여러분 앙 기모띠!!!

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

문제

문제

출처

ICPC

푸는 방식의 문제인지 확인해주세요

snujoon 5년 전 0

adh0463 5년 전 1

yukino 5년 전 3

snujoon 5년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말