【郑轻】[1900]985的“树”难题

问题描述

985的“树”难题

时间限制：1 Sec内存限制：128 MB

Description

985给你一棵“树”以及它的根节点，要求你先判定它是否是一棵树，其次他想知道每个节点的“太子”数目以及它的父亲（root的话输出自己）。
“太子判定条件”：
一、若x是y的孩子节点，那么x是y的“太子”；
二、若x是y的“太子”且y是z的“太子”，那么x是z的“太子”。

Input

第一行输入一个整数t，代表有t组测试数据。
每组数据第一行输入两个整数n，root分别代表树的节点数目以及根节点的编号。
接下来n-1行，每行输出两个整数u，v代表u节点和v节点之间有一条树边。
注：1 <= t <= 20，1 <= n <= 1e4，1 <= root <= n，1 <= u，v <= n。

Output

对每一组数据，若给定的“树”不合法输出NO即可，反之输出YES，接下来输出占两行：
第一行输出n个整数代表每个节点的“太子”数目，
第二行输出n个整数代表每个节点的父亲节点编号。
输出顺序从1到n，每两个数之间有一个空格，最后一个数后面没有空格。

Sample Input

Sample Output

  YES
2 1 0
1 1 2
NO

问题分析

-.-证明我不适合比赛的一题
宇神称之为签到题
事实上涉及到了一些知识点也不复杂
DFS、并查集、邻接表
DFS用来递归查找下一节点
并查集用来更新节点的深度和父节点的信息
邻接表用来优化数据结构
1、读取输入存入邻接表
2、以root为起点DFS下一节点
3、以并查集思想把下一节点的父节点设为这一节点
最后用find函数来更新根的深度

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<stdio.h>
#include<string.h>
int head[10200];
int headcnt;
bool win;
struct List {
	int u,v;
	int next;
} edge[20200];
int n,root;
int par[10200];
int ran[10200];
int flag[10200];
int find(int m) {
	if(m==par[m])
		return m;
	else {
		ran[par[m]]++;
		return find(par[m]);
	}
}
void unite(int x,int y) {
	par[y]=x;
}
void dfs(int u) {
	for(int i=head[u]; i!=-1; i=edge[i].next) {
		if(!flag[edge[i].v]&&edge[i].v!=par[u]) {
			unite(u,edge[i].v);
			flag[edge[i].v]=1;
			dfs(edge[i].v);
		}
	}
}
void add(int u,int v) {
	edge[headcnt].u=u;
	edge[headcnt].v=v;
	edge[headcnt].next=head[u];
	head[u]=headcnt++;
}
int main() {
	int T;
	scanf("%d",&T);
	while(T--) {
		scanf("%d %d",&n,&root);
		headcnt=0;
		memset(head,-1,sizeof(head));
		memset(flag,0,sizeof(flag));
		for(int i=1; i<=n; i++) {
			par[i]=i;
			ran[i]=0;
		}
		for(int i=1; i<n; i++) {
			int u,v;
			scanf("%d %d",&u,&v);
			add(u,v);
			add(v,u);
		}
		win=true;
		flag[root]=1;
		dfs(root);
		if(win) {
			for(int i=1; i<=n; i++)
				if(find(i)!=root) {
					win=false;
					break;
				}
		}
		if(win) {
			printf("YES\n");
			for(int i=1; i<=n; i++) {
				printf("%d",ran[i]);
				if(i==n)
					printf("\n");
				else
					printf(" ");
			}
			for(int i=1; i<=n; i++) {
				printf("%d",par[i]);
				if(i==n)
					printf("\n");
				else
					printf(" ");
			}
		} else
			printf("NO\n");
	}
	return 0;
}

题目地址:【郑轻】[1900]985的“树”难题