POJ3630Phone List(字典树)

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <vector>
 8 #include <cstdio>
 9 #include <cctype>
10 #include <cstring>
11 #include <cstdlib>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 #define INF 0x3f3f3f3f
16 #define MAX(a,b) (a > b ? a : b)
17 #define MIN(a,b) (a < b ? a : b)
18 #define mem0(a) memset(a,0,sizeof(a))
19 #define mem1(a) memset(a,-1,sizeof(a))
20 #define lson k<<1, L, mid
21 #define rson k<<1|1, mid+1, R
22 
23 typedef long long LL;
24 const double eps = 1e-12;
25 const int MAXN = 100005;
26 const int MAXM = 500005;
27 
28 int T, n, tree[100010][12], now;
29 char s[12];
30 
31 bool addToTree(char* str)//添加成功返回true，产生矛盾返回false
32 {
33     int last = 0;
34     for(int i=0;str[i];i++)
35     {
36         int num = str[i]-‘0‘;
37         if(tree[last][num]>0)last=tree[last][num];//这条路已经存在，沿着这条路走
38         else if(tree[last][num]==0)//还没走过
39         {
40             tree[last][num]=++now;//建一条新的边
41             last = now;//
42         }
43         else if(tree[last][num]==-1)return false;//产生矛盾
44     }
45     for(int i=0;i<10;i++)
46         if(tree[now][i]==-1)return false;//有两个人的号码相同
47         else tree[now][i] = -1;//否则的话他之后的所有的都是不可走的
48     return true;
49 }
50 
51 int main()
52 {
53     scanf("%d", &T);
54     while(T--)
55     {
56         now = 0; mem0(tree);
57         scanf("%d", &n);
58         bool danger=false;
59         for(int i=0;i<n;i++)
60         {
61             scanf("%s", s);
62             if(!danger && !addToTree(s)) danger = true;
63         }
64         printf("%s\n", danger?"NO":"YES");
65     }
66     return 0;
67 }