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,遍历过程中记录每个节点的父节点就好了。完整代码如下:

#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;
}

本代码提交AC,用时42MS。

Leave a Reply

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