nyoj 230 페인트 막대 및 사전 트리 찾기 오라

색봉

시간 제한:
1000ms | 메모리 제한:
128000 KB
난이도:
오
묘사
You are given a bunch of wooden sticks. Each endpoint of each stick is colored with some color. Is it possible to align the sticks in a straight line such that the colors of the endpoints that touch are of the same color?
입력
the frist line have a number k(0출력
If the sticks can be aligned in the desired way, output a single line saying Possible, otherwise output Impossible.
샘플 입력

1

5

blue red

red violet

cyan blue

blue magenta

magenta cyan

샘플 출력

Possible

#include<stdio.h>

#include<string.h>

#include<malloc.h>

struct node

{

    int order;

    struct node *next[26];

};



int  t;// 

int father[250001];// 

int degree[250001];// 

int insert(char *str,node *T)// 

{

    int len,id,flat=0,i,j;

    node *p,*q;

    len=strlen(str);

    p=T;

    for(i=0;i<len;++i)

    {

        id=str[i]-'a';

        if(p->next[id]==NULL)

        {

            flat=1;

            q=(node *)malloc(sizeof(node));

            for(j=0;j<26;++j)

                q->next[j]=NULL;

            p->next[id]=q;

        }

        p=p->next[id];

    }

    if(flat)// ， 

    {

        p->order=t;//   

        degree[t++]++;// 

        return p->order;

    }

    else

    {

        if(p->order==0)//  abdse abd ， 

        {

            p->order=t;

            degree[t++]++;

            return p->order;

        }

        degree[p->order]++;

        return p->order;

    }

}



int findfather(int i)

{

    if(father[i]==-1)

        return i;

    else

        return findfather(father[i]);

}



void merge(int a,int b)//  

{

    a=findfather(a);

    b=findfather(b);

    if(a!=b)

    {

        if(father[a]<father[b])

            father[b]=a;

        else

            father[a]=b;

    }

}



int main()

{

    char str1[14],str2[14];

    int flag,i,num1,num2,n,x;

    node *T;

    scanf("%d",&x);

    while(x--)

    {

        T=(node *)malloc(sizeof(node));

        T->order=0;

        memset(degree,0,sizeof(degree));

        memset(father,-1,sizeof(father));

        for(i=0;i<26;++i)

            T->next[i]=NULL;

        t=1;

        scanf("%d",&n);

        if(n==0)

        {

            printf("Possible
");

            continue;

        }

        while(n--)

        {

            scanf("%s%s",str1,str2);

            num1=insert(str1,T);

            num2=insert(str2,T);

            merge(num1,num2);

        }

        flag=0;

        for(i=1;i<t;++i)

            if(father[i]==-1)// 

                ++flag;

        if(flag>1)

            printf("Impossible
");

        else

        {

            flag=0;

            for(i=1;i<t;++i)

                if(degree[i]&1)

                    flag++;

            if(flag==2||flag==0)

                 printf("Possible
");

            else

                 printf("Impossible
");

        }

    }

    return 0;

}

눈물이 난다. 처음에 단어와 연결이 비슷하다고 생각하고 그 코드를 조금 바꾸어 시간을 초과했는데, 나중에 뚱뚱한 사람이 사전나무로 쓸 것을 만들고 수집한다고 말했다.그리고 수집은 빅데이터 양에 매우 빠른 효율을 가진다. 이 문제는 25만 개의 데이터로 보아 바로 이 점을 시험한 것 같다.쓰고 수집했는데 과연 지나갔다
생각:
먼저 데이터를 사전 트리에 저장하고 사전 트리의 역할은 두 가지가 있다. 하나는 색채 종류를 통계하는 것이고, 하나는 색채 수량이다.그리고 이 색깔들이 합쳐지는 것을 병합하여 수집한다.입력할 때마다 병합됩니다.마지막에 다음 노드의 수량을 통계하면 병렬적으로 수집하는 수량이다. 만약에 1보다 크면 하나의 집합이 아니라 절대로 연결선이 될 수 없다는 것을 의미한다. 만약에 그렇다면 오라 통로의 원리에 따라 판정해야 한다.

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

POJ 2236 Wireless Network 간편한 검색 및 수집

The ACM (Asia Cooperated Medical team) have set up a wireless network with the lap computers, but an unexpected aftersho...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

nyoj 230 페인트 막대 및 사전 트리 찾기 오라

색봉

좋은 웹페이지 즐겨찾기