hdu 1617 Phone List

4194 단어 HDU사전 트리
간단한 사전 트리.메모리를 방출하잖아요.차례차례 돌아오면 된다.루트 조심하세요.
끊겼지만...야, 새벽에 어질어질한 이유지...
깨진 잠, 깨진 잠,
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define maxn 10010
char test[50];
int flag;
struct trie
{
    int v;
    trie *next[10];
    trie()
    {
        v=0;
        for(int i=0;i<10;i++)
        {
            next[i]=NULL;
        }
    }
};
trie *root;
void build(char *str)
{
    int len=strlen(str);
    trie *p=root;
    for(int i=0;i<len;i++)
    {
        int id=str[i]-'0';
        if(p->next[id]==NULL)
        {
            trie *q=new trie;
            p->next[id]=q;
        }
        p=p->next[id];
        if(p->v)
        {
            flag=1;
            return ;
        }
    }
    for(int i=0;i<10;i++)
    {
        if(p->next[i]!=NULL)
        {
            flag=1;
            return ;
        }
    }
    p->v=1;
}
void zhan(trie *p)
{
    if(p==NULL)
        return ;
    for(int i=0;i<10;i++)
    {
        if(p->next[i]!=NULL)
        {
            zhan(p->next[i]);
        }
    }
    delete p;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        flag=0;
        int n;
        cin>>n;
        zhan(root);
        root=new trie;
        for(int i=1;i<=n;i++)
        {
            cin>>test;
            if(flag)
                continue;
            build(test);
        }
        if(!flag)
        {
            cout<<"YES"<<endl;
        }
        else
        {
            cout<<"NO"<<endl;
        }
    }
    return 0;
}

좋은 웹페이지 즐겨찾기