HDU 5432 Rikka with Tree (BestCoder Round #53 (div.2))

http://acm.hdu.edu.cn/showproblem.php?pid=5423

题目大意:给你一个树 判断这棵树是否是独特的

一颗树是独特的条件:不存在一颗和它本身不同但相似的树

两颗树相似条件:两颗树中点的数量相等且相对应的点的深度相同

如第2个样例

4

1 2

2 3

1 4

4

1 2

1 4

3 4

如图:这两棵树的点的数量相等且相应的点的深度deep相同,所以这两棵树相似,所以样例2存在一颗树与它不同但相似,即不特殊

HDU 5432 Rikka with Tree (BestCoder Round #53 (div.2))

运用广搜统计每个点的深度

要想一颗树特殊,只有保证他的分支下面不再有子节点

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 1010 using namespace std; struct Edge
{
int u, v, cnt, next;
}edge[N * N]; int head[N], j, cnt;
int a[N];//记录各个点的深度
bool vis[N]; void Add(int u, int v)//邻接表
{
edge[cnt].u = u;
edge[cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt++;
} void Init()
{
memset(head, -, sizeof(head));
memset(a, , sizeof(a));
memset(vis, false, sizeof(vis));
cnt = j = ;
} void DFS(int u, int deep)
{
int v, i;
vis[u] = true;
for(i = head[u]; i != - ; i = edge[i].next)
{
v = edge[i].v;
if(!vis[v])
{
vis[v] = true;
DFS(v, deep + );
}
}
a[j++] = deep;
return ;
}//查找记录各个点的深度 int cmp(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
} int main()
{
int n, u, v;
while(~scanf("%d", &n))
{
Init();
for(int i = ; i < n ; i++)
{
scanf("%d%d", &u, &v);
Add(u, v);
Add(v, u);
}
DFS(, );
qsort(a, j, sizeof(a[]), cmp);
int deep = , f = , fl = ;
for(int i = ; i < j ; i++)
{
if(a[i - ] == a[i])
{
fl = ;//如果两个点的深度相同,就存在分支,即标记有分支
deep = a[i];
}
if(fl == && a[i] > deep)
f = ;//如果存在分支且分支的下面还有节点则输出NO
}
if(f == )
printf("YES\n");
else
printf("NO\n");
}
return ;
}
上一篇:pandas 0.19.0 documentation


下一篇:html圆角提示效果