-
Notifications
You must be signed in to change notification settings - Fork 0
/
treediam.cc
139 lines (131 loc) · 3.42 KB
/
treediam.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <map>
using namespace std;
typedef array<int, 2> edge_t;
typedef vector<edge> vedge_t;
typedef vector<int> vi_t;
class Node {
public:
Node(int _parent = -1) : parent(_parent) {}
// int id;
int parent;
vi_t child;
};
typedef vector<Node> vnode_t; // tree
typedef map<int, Node> i2node_t;
void build_tree(int& root, i2node_t& tree, const vedge_t& edges) {
for (const edge_t& e: edges) {
if (tree.empty()) {
root = edge[0];
Node noderoot;
noderoot.child.push_back(edge[1]);
tree.insert(tree.end(), i2node_t::value_type(root, noderoot));
tree.insert(tree.end(), i2node_t::value_type(edge[1], Node()));
} else {
if (edge[1] == root) {
swap(edge[0], edge[1]);
}
i2node::iterator iters[2];
for (int i = 0; i < 2; ++i) {
iter[i] = tree.find(e[i]);
if (iter[i) == tree.end()) {
iter[i] = tree.insert(tree.end(), Node());
}
}
iter[0]->second.child.push_back(edge[1]);
}
}
}
int my_depth(const i2node_t& tree, int inode) {
int d = 0;
for (i2node_t::iterator iter = tree.find(inode);
iter != tree.end(); iter = tree.find(iter->second.parent), ++d)
{}
return d;
}
int #include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <map>
using namespace std;
typedef array<int, 2> edge_t;
typedef vector<edge> vedge_t;
typedef vector<int> vi_t;
class Node {
public:
Node(int _parent = -1) : parent(_parent) {}
// int id;
int parent;
vi_t child;
};
typedef vector<Node> vnode_t; // tree
typedef map<int, Node> i2node_t;
void build_tree(int& root, i2node_t& tree, const vedge_t& edges) {
for (const edge_t& e: edges) {
if (tree.empty()) {
root = edge[0];
Node noderoot;
noderoot.child.push_back(edge[1]);
tree.insert(tree.end(), i2node_t::value_type(root, noderoot));
tree.insert(tree.end(), i2node_t::value_type(edge[1], Node()));
} else {
if (edge[1] == root) {
swap(edge[0], edge[1]);
}
i2node::iterator iters[2];
for (int i = 0; i < 2; ++i) {
iter[i] = tree.find(e[i]);
if (iter[i) == tree.end()) {
iter[i] = tree.insert(tree.end(), Node());
}
}
iter[0]->second.child.push_back(edge[1]);
}
}
}
int upepth(const i2node_t& tree, int inode) {
int d = 0;
for (i2node_t::iterator iter = tree.find(inode);
iter != tree.end(); iter = tree.find(iter->second.parent), ++d)
{}
return d;
}
int depth(const i2node_t& tree, int inode) {
int d = 0;
const Node& node = tree.find(inode)->second;
for (int c: node.child) {
int cdepth = depth(tree, c);
if (d < cdepth + 1) {
d = cdepth + 1;
}
}
return d;
}
void depth_diam(int &depth, int diam, const i2node_t& tree, int inode) {
int d = 0;
vi_t max_depths;
const Node& node = tree.find(inode)->second;
for (int c: node.child) {
int cdepth = 0, cidam = 0;
depth_diam(cdepth, cdiam, tree, c);
if (diam < cdiam) { diam = cdiam; }
max_depths.push_back(cdepth);
sort(max_depths.begin(), max_depths.end(), greater<int>);
if (max_depths.size() > 2) {
max_depths.pop_back()
}
if (d < cdepth + 1) {
d = cdepth + 1;
}
}
int sub_diam = accumulate(max_depths.begin(), max_depths.end(), 0);
if (diam < sub_diam) { diam = sub_diam; }
}
int main(int argc, char** argv) {
int ret = 0;
return ret;
}