AcWing 161. 电话列表
原题链接
简单
作者:
神风游骑兵
,
2022-06-27 01:18:02
,
所有人可见
,
阅读 238
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e4+10,M=1e5+10;
int son[M][10];
int st[M];
char s[N];
int n,m,idx,flag;
inline void add(char x[]){
int l=strlen(x);
int p=0,u;
for(int i=0;i<l;i++){
u=x[i]-'0';
if(!son[p][u])son[p][u]=++idx;
p=son[p][u];
}
st[p]++;
}
inline void dfs(int p){
if(flag)return ;
if(st[p]>1){flag=1;return;}
else if(st[p]==1){
for(int i=0;i<=9;i++){
if(son[p][i]){flag=1;return;}
}
}
for(int i=0;i<=9;i++)
{
if(!son[p][i])continue;
dfs(son[p][i]);
}
}
int main(){
int T;
cin>>T;
while(T--)
{ idx=0;
int n;
cin>>n;
memset(son,0,sizeof son);
memset(st,0,sizeof st);
for(int i=0;i<n;i++){
scanf("%s",s);
add(s);
}
dfs(0);
if(!flag)puts("YES");
else puts("NO");
flag=0;
}
}