NC99. 多叉树的直径
描述
示例1
输入:
6,[[0,1],[1,5],[1,2],[2,3],[2,4]],[3,4,2,1,5]
输出:
11
示例2
输入:
3,[[0,1],[1,2]],[1,1]
输出:
2
C++ 解法, 执行用时: 12ms, 内存消耗: 2496KB, 提交时间: 2021-08-06
static const auto io_sync_off = []()
{
// turn off sync
std::ios::sync_with_stdio(false);
// untie in/out streams
std::cin.tie(nullptr);
return nullptr;
}();
/**
* struct Interval {
* int start;
* int end;
* };
*/
class Solution {
public:
int max_diameter;
/**
* 树的直径
* @param n int整型 树的节点个数
* @param Tree_edge Interval类vector 树的边
* @param Edge_value int整型vector 边的权值
* @return int整型
*/
int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value) {
// write code here
vector<vector<pair<int, int>>> record(n);
int len = n-1;
for(int i=0; i<len; i++){
Interval &edge = Tree_edge[i];
record[ edge.start ].push_back( {edge.end, Edge_value[i]} );
record[ edge.end ].push_back( {edge.start, Edge_value[i]} );
}
max_diameter = 0;
my_rear_ergodic(record, -1, 0);
return max_diameter;
}
int my_rear_ergodic(vector<vector<pair<int, int>>> &record, int last_node_id, int node_id){
int max_1 = 0, max_2 = 0, tmp;
for(auto &i_i_pair : record[node_id])
if(i_i_pair.first != last_node_id){
if((tmp = my_rear_ergodic(record, node_id, i_i_pair.first)+i_i_pair.second) > max_1)
{ max_2 = max_1; max_1 = tmp; continue; }
if(tmp > max_2) max_2 = tmp;
}
if((tmp = max_1+max_2) > max_diameter) max_diameter = tmp;
return max_1;
}
};//mean ken lopk someonebba onantan
C++ 解法, 执行用时: 14ms, 内存消耗: 2380KB, 提交时间: 2021-06-30
static const auto io_sync_off = []()
{
// turn off sync
std::ios::sync_with_stdio(false);
// untie in/out streams
std::cin.tie(nullptr);
return nullptr;
}();
/**
* struct Interval {
* int start;
* int end;
* };
*/
class Solution {
public:
int max_diameter;
/**
* 树的直径
* @param n int整型 树的节点个数
* @param Tree_edge Interval类vector 树的边
* @param Edge_value int整型vector 边的权值
* @return int整型
*/
int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value) {
// write code here
vector<vector<pair<int, int>>> record(n);
int len = n-1;
for(int i=0; i<len; i++){
Interval &edge = Tree_edge[i];
record[ edge.start ].push_back( {edge.end, Edge_value[i]} );
record[ edge.end ].push_back( {edge.start, Edge_value[i]} );
}
max_diameter = 0;
my_rear_ergodic(record, -1, 0);
return max_diameter;
}
int my_rear_ergodic(vector<vector<pair<int, int>>> &record, int last_node_id, int node_id){
int max_1 = 0, max_2 = 0, tmp;
for(auto &i_i_pair : record[node_id])
if(i_i_pair.first != last_node_id){
if((tmp = my_rear_ergodic(record, node_id, i_i_pair.first)+i_i_pair.second) > max_1)
{ max_2 = max_1; max_1 = tmp; continue; }
if(tmp > max_2) max_2 = tmp;
}
if((tmp = max_1+max_2) > max_diameter) max_diameter = tmp;
return max_1;
}
};
C++ 解法, 执行用时: 15ms, 内存消耗: 2460KB, 提交时间: 2021-09-10
/**
* struct Interval {
* int start;
* int end;
* };
*/
//bug version
class Solution1 {
public:
/**
* 树的直径
* @param n int整型 树的节点个数
* @param Tree_edge Interval类vector 树的边
* @param Edge_value int整型vector 边的权值
* @return int整型
*/
int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value)
{
vector<pair<int,int>> row;
vector<vector<pair<int,int>>> dp(n, row);
for(int i=0; i<Tree_edge.size(); ++i)
{
int first = Tree_edge[i].start;
int second = Tree_edge[i].end;
dp[first].push_back({second, Edge_value[i]});
dp[second].push_back({first, Edge_value[i]});
}
int maxVertexIdx = 0;
int len =0;
int maxlen =0;
bool *marked1 = new bool[n];
dfs(dp, 0 ,marked1, len=0, maxlen=0, maxVertexIdx=0);
cout<<maxlen<<endl;
cout<<maxVertexIdx << endl;
bool *marked2 = new bool[n];
dfs(dp, maxVertexIdx, marked2, len, maxlen, maxVertexIdx);
return maxlen;
}
void dfs(vector<vector<pair<int,int>>> &graph, int srcVertexId, bool *marked, int len, int &maxlen, int &maxVertexIdx)
{
marked[srcVertexId] = true;
for(vector<pair<int,int>>::iterator it = graph[srcVertexId].begin(); it != graph[srcVertexId].end(); ++it)
{
if(!marked[(*it).first])
{
if(len +(*it).second > maxlen)
{
maxlen = len+(*it).second;
maxVertexIdx = (*it).first;
}
dfs(graph, (*it).first, marked, len + (*it).second, maxlen,maxVertexIdx);
}
}
}
};
/**
* struct Interval {
* int start;
* int end;
* };
*/
class Solution2 {
private:
vector<vector<pair<int, int>>> graph;
int max_dist = 0, max_idx = 0;
public:
// 两次DFS，需要看证明过程
int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value) {
// write code here
// 建立图，采用邻接表的格式
graph.resize(n);
int e_n = Tree_edge.size();
for (int i = 0; i < e_n; ++i) {
int node1 = Tree_edge[i].start;
int node2 = Tree_edge[i].end;
graph[node1].emplace_back(node2, Edge_value[i]);
graph[node2].emplace_back(node1, Edge_value[i]);
}
// 第一次从任意节点开始，找距离最远的节点A
dfs(0, -1, 0);
// 第二次从A出发，寻找距离最远的节点
dfs(max_idx, -1, 0);
return max_dist;
}
void dfs(int cur, int parent, int dist) {
for (auto& e : graph[cur]) {
if (e.first != parent) {
dfs(e.first, cur, dist + e.second);
}
}
if (dist > max_dist) {
max_dist = dist;
max_idx = cur;
}
}
};
//improvement version
class Solution {
public:
/**
* 树的直径
* @param n int整型 树的节点个数
* @param Tree_edge Interval类vector 树的边
* @param Edge_value int整型vector 边的权值
* @return int整型
*/
int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value)
{
vector<vector<pair<int, int>>> graph(n);
for(int i=0; i < Tree_edge.size(); ++i)
{
int start = Tree_edge[i].start;
int end = Tree_edge[i].end;
graph[start].push_back({end, Edge_value[i]});
graph[end].push_back({start, Edge_value[i]});
}
pair<int, int> pair_dfs_first = dfs(graph, 0, -1, 0);
cout << pair_dfs_first.first << endl;
pair<int, int> pair_dfs_second = dfs(graph, pair_dfs_first.first, -1, 0);
return pair_dfs_second.second;
}
pair<int, int> dfs(vector<vector<pair<int, int>>> &graph, int currentVertex, int parrentVertex, int currentDist)
{
int max_dist_id = currentVertex;
int max_dist = currentDist;
for(vector<pair<int,int>>::iterator it = graph[currentVertex].begin();
it != graph[currentVertex].end(); ++it)
{
if(it->first != parrentVertex)
{
pair<int, int> pair_dfs = dfs(graph, it->first, currentVertex, currentDist+it->second);
if(pair_dfs.second > max_dist)
{
max_dist = pair_dfs.second;
max_dist_id = pair_dfs.first;
}
}
}
return {max_dist_id, max_dist};
}
};
C++ 解法, 执行用时: 15ms, 内存消耗: 2472KB, 提交时间: 2021-09-19
/**
* struct Interval {
* int start;
* int end;
* };
*/
class Solution {
public:
/**
* 树的直径
* @param n int整型 树的节点个数
* @param Tree_edge Interval类vector 树的边
* @param Edge_value int整型vector 边的权值
* @return int整型
*/
vector<vector<pair<int, int>>> graph;
int maxn = 0, idx;
void dfs(int cur, int parent, int sum) {
if(maxn < sum) {
maxn = sum;
idx = cur;
}
for (auto n:graph[cur]) {
if(n.first != parent)
dfs(n.first, cur, sum+n.second);
}
}
int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value) {
// write code here
graph.resize(n);
for(int i = 0; i < Tree_edge.size(); i++) {
int node1 = Tree_edge[i].start;
int node2 = Tree_edge[i].end;
graph[node1].emplace_back(node2, Edge_value[i]);
graph[node2].emplace_back(node1, Edge_value[i]);
}
dfs(0, -1, 0);
dfs(idx, -1, 0);
return maxn;
}
};
C++ 解法, 执行用时: 15ms, 内存消耗: 2508KB, 提交时间: 2021-08-02
/**
* struct Interval {
* int start;
* int end;
* };
*/
class Solution {
public:
/**
* 树的直径
* @param n int整型 树的节点个数
* @param Tree_edge Interval类vector 树的边
* @param Edge_value int整型vector 边的权值
* @return int整型
*/
vector<vector<pair<int, int>>> edges;
int result = 0;
int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value) {
edges = vector<vector<pair<int, int>>>(n, vector<pair<int, int>>(0));
for (int i = 0; i + 1 < n; i++) {
int start = Tree_edge[i].start, end = Tree_edge[i].end;
edges[start].push_back({end, Edge_value[i]});
edges[end].push_back({start, Edge_value[i]});
}
dfs(-1, 0);
return result;
}
int dfs(int parent, int self) {
priority_queue<int, vector<int>, greater<>> pq;
for (const auto &child : edges[self]) {
if (child.first == parent)
continue;
int len = child.second + dfs(self, child.first);
if (pq.size() < 2) {
pq.push(len);
} else if (len > pq.top()) {
pq.push(len);
pq.pop();
}
}
int a = 0, b = 0;
if (pq.size() > 0) {
a = pq.top();
pq.pop();
}
if (pq.size() > 0)
b = pq.top();
result = max(result, a + b);
return max(a, b);
}
};