当前位置： 移动技术网 > 移动技术>移动开发>IOS > 2020多校联赛，第二场C-Cover the Tree

2020多校联赛，第二场C-Cover the Tree

2020年07月23日  | 移动技术网移动技术  | 我要评论

题意

给定一个无根树。如何将树的边缘都至少被一条链所覆盖
题意比赛时理解错了，最后树，只要两个边缘的叶子节点连接在一起就可以，之前以为要将所有边缘点连接在一起。

解题思路

首先从一个非叶子节点出发，通过dfs寻找所有叶子节点，存起来，之后两两相连即可，当初存储方式有些问题，内存过大。最后输出也理解错了，现在看来还可以。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<string>
#include<deque>
const int mod = 998244353;
using namespace std;
typedef long long ll;
vector<int> tree[500000], Q;
int mins = 99999999;
void dfs(int root,int fa)
{
	if (tree[root].size() == 1)
		Q.push_back(root);
	for (int i = 0; i < tree[root].size(); i++)
	{
		if (tree[root][i] != fa)
		{
			dfs(tree[root][i], root);
		}
	}
}
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie();
	int n;
	cin >> n;
	int sum = 0;
		for (int i = 1; i < n; i++)
		{
			int root;
			cin >> root;
			int zi;
			cin >> zi;
			tree[root].push_back(zi);
			tree[zi].push_back(root);
		}
		int root = 1;
		while (tree[root].size() == 1)
			root++;
		dfs(root, -1);
		int load = -1;
		cout << (Q.size()+1)/2<<endl;
		for (int i = 0; i < (Q.size()+1)/2; i++)
			cout<<Q[i]<< ' '<<Q[(i + Q.size() / 2) % Q.size()]<<endl;
}

本文地址：https://blog.csdn.net/weixin_43832788/article/details/107406820

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网