「Solution」叶子清除计划【第五周】

叶子清除计划【第五周】

题目描述

⼩Y同学是⼀位数据结构⼤师同时也是⼀位园艺⼤师。

秋天到了，⼩Y同学需要对学校内的⼀棵树展现他顶尖的修叶⽔平。

学校内的这棵树是⼀颗拥有n个点的⽆根树，每次⼩Y会删去所有的叶⼦节点（即度数小于等于1的节点)，直到所有的点都被删除了为⽌。

⼩Y现在想问你对于每个点，求出它是第⼏次操作中被删除的。

输入格式

第⼀⾏⼀个数字n，表⽰树上节点个数

接下来n−1⾏，每⾏两个数字u,v，表⽰树上的⼀条边。

输出格式

⼀⾏n个数字，第i个数字表⽰节点i在第⼏次操作中被删除。

样例

样例输入1:

5
1 2
1 3
2 4
2 5

样例输出1:

2 2 1 1 1

样例输入2:

4
1 2
1 3
1 4

样例输出2:

2 1 1 1

数据范围与提示

对于30%的数据，n≤1000

对于100%的数据，2≤n≤100000,1≤u,v≤n

分析

首先看到题目，所给树是一棵无根树,一棵没有特定的根节点的树，称为无根树。
所以任意选取图中某个点为根，均可将无根树转化成为有根树，即在输入时要双向加边。
因为每次是要将叶子节点删去，那么当入度为1时（假设此边所连点为根节点，此节点就是叶子节点），就应该删掉。
题目要求删除的顺序，所以就定义一个结构体，保存入度和删除的次序，通过以上推论可得删掉的节点的次序就应该是它倒数第二条边所连接的节点的次序加一。
用拓扑序变形就可解决。
分析至此，不难写出代码.

代码

#include <queue>
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 100005;

int n;
vector<int> G[MAXN]; 

struct node {
	int in, flo;
} a[MAXN];

queue<int> q;

void topsort() {
	for (int i = 1; i <= n; i++) {
		if (a[i].in == 1) {
			q.push(i);
			a[i].flo = 1;
		}
	}
	while (q.size()) {
		int u = q.front();
		q.pop();
//		printf ("%d: ", u);
		for (int i = 0; i < G[u].size(); i++) {
			int v = G[u][i];
			a[v].in --;
			if (a[v].in == 1) {
//				printf ("%d ", v);
				a[v].flo = a[u].flo + 1;
				q.push(v);
			}
		}
//		printf ("\n");
	}
}

int main() {
	scanf ("%d", &n);
	for (int i = 1, u, v; i < n; i++) {
		scanf ("%d %d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
		a[u].in ++, a[v].in ++;
	}
//	for (int i = 1; i <= n; i++) {
//		printf ("%d %d\n", a[i].flo, a[i].in);
//	}
	topsort();
	for (int i = 1; i <= n; i++) {
		printf ("%d ", a[i].flo);
	}
	return 0;
}