hihoCoder 1542-无根数变有根树
#1542 : 无根数变有根树
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
给定一棵包含 N 个节点的无根树，小Hi想知道如果指定其中某个节点 K 为根，那么每个节点的父节点是谁？
输入
第一行包含一个整数 N 和 K。1 ≤ N ≤ 1000, 1 ≤ K ≤ N。 以下N-1行每行包含两个整数 a 和 b，代表ab之间存在一条边。 1 ≤ a, b ≤ 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。]]>