hihoCoder 1542-无根数变有根树

hihoCoder 1542-无根数变有根树

#1542 : 无根数变有根树

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

给定一棵包含 N 个节点的无根树,小Hi想知道如果指定其中某个节点 K 为根,那么每个节点的父节点是谁?

输入

第一行包含一个整数 N 和 K。1 ≤ N ≤ 1000, 1 ≤ K ≤ N。 以下N-1行每行包含两个整数 a 和 b,代表ab之间存在一条边。 1 ≤ ab ≤ N。 输入保证是一棵树。

输出

输出一行包含 N 个整数,分别代表1~N的父节点的编号。对于 K 的父节点输出0。
样例输入
5 4
1 2
3 1
4 3
5 1
样例输出
3 1 4 0 1

给定一个无根树(其实就是DAG),如果以该树的某个顶点K为根,要求输出每个节点的父节点。 简单题,以K为根,进行DFS,遍历过程中记录每个节点的父节点就好了。完整代码如下: [cpp] #include<iostream> #include<vector> #include<algorithm> #include<unordered_set> #include<string> #include<unordered_map> #include<queue> using namespace std; const int kMaxN = 1005; int n, k; vector<int> parent(kMaxN, 0); vector<vector<int>> graph(kMaxN, vector<int>(kMaxN, 0)); void DFS(int node, int pre) { parent[node] = pre; graph[node][pre] = 0; graph[pre][node] = 0; for (int i = 1; i <= n; ++i) { if (graph[node][i] == 1) { DFS(i, node); } } graph[node][pre] = 1; graph[pre][node] = 1; } int main() { //freopen("input.txt", "r", stdin); scanf("%d %d", &n, &k); int a, b; for (int i = 0; i < n – 1; ++i) { scanf("%d %d", &a, &b); graph[a][b] = 1; graph[b][a] = 1; } DFS(k, 0); for (int i = 1; i <= n; ++i) printf("%d ", parent[i]); return 0; } [/cpp] 本代码提交AC,用时42MS。]]>

Leave a Reply

Your email address will not be published. Required fields are marked *