A country network consisting of N cities and N − 1 roads connecting them is given. Cities are labeled with distinct integers within the range [0..(N − 1)]. Roads connect cities in such a way that each distinct pair of cities is connected either by a direct road or through a path consisting of direct roads. There is exactly one way to reach any city from any other city.
Starting out from city K, you have to plan a series of daily trips. Each day you want to visit a previously unvisited city in such a way that, on a route to that city, you will also pass through a maximal number of other unvisited cities (which will then be considered to have been visited). We say that the destination city is our daily travel target.
In the case of a tie, you should choose the city with the minimal label. The trips cease when every city has been visited at least once.
For example, consider K = 2 and the following network consisting of seven cities and six roads:
You start in city 2. From here you make the following trips:
- day 1 − from city 2 to city 0 (cities 1 and 0 become visited),
- day 2 − from city 0 to city 6 (cities 4 and 6 become visited),
- day 3 − from city 6 to city 3 (city 3 becomes visited),
- day 4 − from city 3 to city 5 (city 5 becomes visited).
The goal is to find the sequence of travel targets. In the above example we have the following travel targets: (2, 0, 6, 3, 5).
Write a function:
vector<int> solution(int K, vector<int> &T);
that, given a non-empty array T consisting of N integers describing a network of N cities and N − 1 roads, returns the sequence of travel targets.
Array T describes a network of cities as follows:
- if T[P] = Q and P ≠ Q, then there is a direct road between cities P and Q.
For example, given the following array T consisting of seven elements (this array describes the network shown above) and K = 2:
T[0] = 1 T[1] = 2 T[2] = 3 T[3] = 3 T[4] = 2 T[5] = 1 T[6] = 4the function should return a sequence [2, 0, 6, 3, 5], as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..90,000];
- each element of array T is an integer within the range [0..(N−1)];
- there is exactly one (possibly indirect) connection between any two distinct roads.
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
class Node {
private:
int m_label;
int m_parent;
bool m_visited;
set<int> m_children;
public:
static int const NO_PARENT = -1;
Node(int label) : m_label(label), m_parent(NO_PARENT), m_visited(false) {
}
int label() const {
return m_label;
}
int parent() const {
return m_parent;
}
void setParent(int parent) {
m_parent = parent;
}
const set<int>& children() const {
return m_children;
}
void addChild(int nodeId) {
m_children.insert(nodeId);
}
void removeChild(int nodeId) {
m_children.erase(nodeId);
}
bool leaf() const {
return m_children.empty() && m_parent != NO_PARENT;
}
bool root() const {
return m_parent == NO_PARENT;
}
bool visited() const {
return m_visited;
}
void setVisited(bool visited) {
m_visited = visited;
}
};
class Tree {
private:
int m_root;
vector<Node> m_nodes;
public:
Tree(int root, const vector<Node>& nodes) : m_root(root), m_nodes(nodes) {
}
int root() const {
return m_root;
}
const vector<Node>& nodes() const {
return m_nodes;
}
const Node& getNode(int node) const {
return m_nodes[node];
}
Node& getNode(int node) {
return m_nodes[node];
}
void changeRoot(int newRootId) {
int nodeId = newRootId;
int oldParentNodeId = getNode(nodeId).parent();
while (nodeId != m_root) {
Node& node = getNode(nodeId);
const int parentNodeId = oldParentNodeId;
Node& parentNode = getNode(parentNodeId);
oldParentNodeId = parentNode.parent();
parentNode.setParent(nodeId);
parentNode.removeChild(nodeId);
node.addChild(parentNodeId);
nodeId = parentNodeId;
}
Node& newRoot = getNode(newRootId);
newRoot.setParent(Node::NO_PARENT);
m_root = newRootId;
}
static Tree make(const vector<int>& edges) {
vector<Node> nodes;
nodes.reserve(edges.size());
for (int i = 0; i < (int) edges.size(); i++) {
const Node node(i);
nodes.push_back(node);
}
int root;
for (int i = 0; i < (int) edges.size(); i++) {
const int j = edges[i];
if (i != j) {
nodes[i].setParent(j);
nodes[j].addChild(i);
} else {
root = i;
}
}
return Tree(root, nodes);
}
};
void removeNonLeaves(const Tree& tree, vector<int>& nodes) {
for (vector<int>::iterator it = nodes.begin(); it != nodes.end(); ) {
const Node& node = tree.getNode(*it);
if (!node.leaf()) {
it = nodes.erase(it);
} else {
++it;
}
}
}
vector<vector<int> > createLevels(const Tree& tree) {
vector<vector<int> > levels;
vector<int> level0; level0.push_back(tree.root());
levels.push_back(level0);
vector<int> currLevel;
while (! (*(levels.end() - 1)).empty() ) {
const vector<int>& prevLevel = *(levels.end() - 1);
for (vector<int>::const_iterator it = prevLevel.begin();
it != prevLevel.end(); ++it) {
const Node& node = tree.getNode(*it);
currLevel.insert(currLevel.begin(), node.children().begin(),
node.children().end());
}
levels.push_back(currLevel);
currLevel.clear();
}
levels.pop_back();
for (size_t i = 0; i < levels.size(); i++) {
removeNonLeaves(tree, levels[i]);
}
return levels;
}
int computeActualLevel(const Tree& tree, int nodeId) {
int result = 0;
while (nodeId != tree.root()) {
const Node& node = tree.getNode(nodeId);
if (!node.visited()) {
result++;
nodeId = node.parent();
} else {
break;
}
}
return result;
}
void visit(Tree& tree, int nodeId) {
while (nodeId != tree.root()) {
Node& node = tree.getNode(nodeId);
if (!node.visited()) {
node.setVisited(true);
nodeId = node.parent();
} else {
break;
}
}
}
#include <iostream>
vector<int> solution(int startNode, vector<int>& edges) {
Tree tree = Tree::make(edges);
tree.changeRoot(startNode);
vector<vector<int> > levels = createLevels(tree);
vector<int> result; result.push_back(startNode);
for (int i = levels.size() - 1; i >= 0; i--) {
vector<int>& level = levels[i];
sort(level.begin(), level.end());
for (vector<int>::iterator it = level.begin(); it != level.end(); ) {
const int nodeId = *it;
const int actualLevel = computeActualLevel(tree, nodeId);
if (actualLevel != i) {
levels[actualLevel].push_back(nodeId);
it = level.erase(it);
} else {
visit(tree, nodeId);
result.push_back(nodeId);
++it;
}
}
}
return result;
}
#include <algorithm>
#include <vector>
#include <set>
#include <stdexcept>
using namespace std;
class Node {
private:
int m_label;
int m_parent;
bool m_visited;
set<int> m_children;
public:
static int const NO_PARENT = -1;
Node(int label) : m_label(label), m_parent(NO_PARENT), m_visited(false) {
}
int label() const {
return m_label;
}
int parent() const {
return m_parent;
}
void setParent(int parent) {
m_parent = parent;
}
const set<int>& children() const {
return m_children;
}
void addChild(int nodeId) {
m_children.insert(nodeId);
}
void removeChild(int nodeId) {
m_children.erase(nodeId);
}
bool leaf() const {
return m_children.empty() && m_parent != NO_PARENT;
}
bool root() const {
return m_parent == NO_PARENT;
}
bool visited() const {
return m_visited;
}
void setVisited(bool visited) {
m_visited = visited;
}
};
class Tree {
private:
int m_root;
vector<Node> m_nodes;
public:
Tree(int root, const vector<Node>& nodes) : m_root(root), m_nodes(nodes) {
}
int root() const {
return m_root;
}
const vector<Node>& nodes() const {
return m_nodes;
}
const Node& getNode(int node) const {
return m_nodes[node];
}
Node& getNode(int node) {
return m_nodes[node];
}
void changeRoot(int newRootId) {
if (m_root == newRootId) return;
int nodeId = newRootId;
int oldParentNodeId = getNode(nodeId).parent();
while (nodeId != m_root) {
Node& node = getNode(nodeId);
const int parentNodeId = oldParentNodeId;
Node& parentNode = getNode(parentNodeId);
oldParentNodeId = parentNode.parent();
parentNode.setParent(nodeId);
parentNode.removeChild(nodeId);
node.addChild(parentNodeId);
nodeId = parentNodeId;
}
Node& newRoot = getNode(newRootId);
newRoot.setParent(Node::NO_PARENT);
m_root = newRootId;
}
static Tree make(const vector<int>& edges) {
vector<Node> nodes;
nodes.reserve(edges.size());
for (int i = 0; i < (int) edges.size(); i++) {
const Node node(i);
nodes.push_back(node);
}
int root = -1;
for (int i = 0; i < (int) edges.size(); i++) {
const int j = edges[i];
if (i != j) {
nodes[i].setParent(j);
nodes[j].addChild(i);
} else {
root = i;
}
}
if (root == -1) {
throw runtime_error("Invalid tree");
}
return Tree(root, nodes);
}
};
void removeNonLeaves(const Tree& tree, vector<int>& nodes) {
for (vector<int>::iterator it = nodes.begin(); it != nodes.end(); ) {
const Node& node = tree.getNode(*it);
if (!node.leaf()) {
it = nodes.erase(it);
} else {
++it;
}
}
}
vector<vector<int> > createLevels(const Tree& tree) {
vector<vector<int> > levels;
vector<int> level0; level0.push_back(tree.root());
levels.push_back(level0);
vector<int> currLevel;
while (! (*(levels.end() - 1)).empty() ) {
const vector<int>& prevLevel = *(levels.end() - 1);
for (vector<int>::const_iterator it = prevLevel.begin();
it != prevLevel.end(); ++it) {
const Node& node = tree.getNode(*it);
currLevel.insert(currLevel.begin(), node.children().begin(),
node.children().end());
}
levels.push_back(currLevel);
currLevel.clear();
}
levels.pop_back();
for (size_t i = 0; i < levels.size(); i++) {
removeNonLeaves(tree, levels[i]);
}
return levels;
}
int computeActualLevel(const Tree& tree, int nodeId) {
int result = 0;
while (nodeId != tree.root()) {
const Node& node = tree.getNode(nodeId);
if (!node.visited()) {
result++;
nodeId = node.parent();
} else {
break;
}
}
return result;
}
void visit(Tree& tree, int nodeId) {
while (nodeId != tree.root()) {
Node& node = tree.getNode(nodeId);
if (!node.visited()) {
node.setVisited(true);
nodeId = node.parent();
} else {
break;
}
}
}
#include <iostream>
vector<int> solution(int startNode, vector<int>& edges) {
Tree tree = Tree::make(edges);
tree.changeRoot(startNode);
vector<vector<int> > levels = createLevels(tree);
vector<int> result; result.push_back(startNode);
for (int i = levels.size() - 1; i >= 0; i--) {
vector<int>& level = levels[i];
sort(level.begin(), level.end());
for (vector<int>::iterator it = level.begin(); it != level.end(); ) {
const int nodeId = *it;
const int actualLevel = computeActualLevel(tree, nodeId);
if (actualLevel != i) {
levels[actualLevel].push_back(nodeId);
it = level.erase(it);
} else {
visit(tree, nodeId);
result.push_back(nodeId);
++it;
}
}
}
return result;
}
#include <algorithm>
#include <vector>
#include <set>
#include <stdexcept>
using namespace std;
class Node {
private:
int m_label;
int m_parent;
bool m_visited;
set<int> m_children;
public:
static int const NO_PARENT = -1;
Node(int label) : m_label(label), m_parent(NO_PARENT), m_visited(false) {
}
int label() const {
return m_label;
}
int parent() const {
return m_parent;
}
void setParent(int parent) {
m_parent = parent;
}
const set<int>& children() const {
return m_children;
}
void addChild(int nodeId) {
m_children.insert(nodeId);
}
void removeChild(int nodeId) {
m_children.erase(nodeId);
}
bool leaf() const {
return m_children.empty() && m_parent != NO_PARENT;
}
bool root() const {
return m_parent == NO_PARENT;
}
bool visited() const {
return m_visited;
}
void setVisited(bool visited) {
m_visited = visited;
}
};
class Tree {
private:
int m_root;
vector<Node> m_nodes;
public:
Tree(int root, const vector<Node>& nodes) : m_root(root), m_nodes(nodes) {
}
int root() const {
return m_root;
}
const vector<Node>& nodes() const {
return m_nodes;
}
const Node& getNode(int node) const {
return m_nodes[node];
}
Node& getNode(int node) {
return m_nodes[node];
}
void changeRoot(int newRootId) {
if (m_root == newRootId) return;
int nodeId = newRootId;
int oldParentNodeId = getNode(nodeId).parent();
while (nodeId != m_root) {
Node& node = getNode(nodeId);
const int parentNodeId = oldParentNodeId;
Node& parentNode = getNode(parentNodeId);
oldParentNodeId = parentNode.parent();
parentNode.setParent(nodeId);
parentNode.removeChild(nodeId);
node.addChild(parentNodeId);
nodeId = parentNodeId;
}
Node& newRoot = getNode(newRootId);
newRoot.setParent(Node::NO_PARENT);
m_root = newRootId;
}
static Tree make(const vector<int>& edges) {
vector<Node> nodes;
nodes.reserve(edges.size());
for (int i = 0; i < (int) edges.size(); i++) {
const Node node(i);
nodes.push_back(node);
}
int root = -1;
for (int i = 0; i < (int) edges.size(); i++) {
const int j = edges[i];
if (i != j) {
nodes[i].setParent(j);
nodes[j].addChild(i);
} else {
root = i;
}
}
if (root == -1) {
throw runtime_error("Invalid tree");
}
return Tree(root, nodes);
}
};
void removeNonLeaves(const Tree& tree, vector<int>& nodes) {
for (vector<int>::iterator it = nodes.begin(); it != nodes.end(); ) {
const Node& node = tree.getNode(*it);
if (!node.leaf()) {
it = nodes.erase(it);
} else {
++it;
}
}
}
vector<vector<int> > createLevels(const Tree& tree) {
vector<vector<int> > levels;
vector<int> level0; level0.push_back(tree.root());
levels.push_back(level0);
vector<int> currLevel;
while (! (*(levels.end() - 1)).empty() ) {
const vector<int>& prevLevel = *(levels.end() - 1);
for (vector<int>::const_iterator it = prevLevel.begin();
it != prevLevel.end(); ++it) {
const Node& node = tree.getNode(*it);
currLevel.insert(currLevel.begin(), node.children().begin(),
node.children().end());
}
levels.push_back(currLevel);
currLevel.clear();
}
levels.pop_back();
for (size_t i = 0; i < levels.size(); i++) {
removeNonLeaves(tree, levels[i]);
}
return levels;
}
int computeActualLevel(const Tree& tree, int nodeId) {
int result = 0;
while (nodeId != tree.root()) {
const Node& node = tree.getNode(nodeId);
if (!node.visited()) {
result++;
nodeId = node.parent();
} else {
break;
}
}
return result;
}
void visit(Tree& tree, int nodeId) {
while (nodeId != tree.root()) {
Node& node = tree.getNode(nodeId);
if (!node.visited()) {
node.setVisited(true);
nodeId = node.parent();
} else {
break;
}
}
}
#include <iostream>
vector<int> solution(int startNode, vector<int>& edges) {
Tree tree = Tree::make(edges);
tree.changeRoot(startNode);
vector<vector<int> > levels = createLevels(tree);
vector<int> result; result.push_back(startNode);
for (int i = levels.size() - 1; i >= 0; i--) {
vector<int>& level = levels[i];
sort(level.begin(), level.end());
for (vector<int>::iterator it = level.begin(); it != level.end(); ) {
const int nodeId = *it;
const int actualLevel = computeActualLevel(tree, nodeId);
if (actualLevel != i) {
levels[actualLevel].push_back(nodeId);
it = level.erase(it);
} else {
visit(tree, nodeId);
result.push_back(nodeId);
++it;
}
}
}
return result;
}
#include <algorithm>
#include <vector>
#include <set>
#include <stdexcept>
using namespace std;
class Node {
private:
int m_label;
int m_parent;
bool m_visited;
set<int> m_children;
public:
static int const NO_PARENT = -1;
Node(int label) : m_label(label), m_parent(NO_PARENT), m_visited(false) {
}
int label() const {
return m_label;
}
int parent() const {
return m_parent;
}
void setParent(int parent) {
m_parent = parent;
}
const set<int>& children() const {
return m_children;
}
void addChild(int nodeId) {
m_children.insert(nodeId);
}
void removeChild(int nodeId) {
m_children.erase(nodeId);
}
bool leaf() const {
return m_children.empty() && m_parent != NO_PARENT;
}
bool root() const {
return m_parent == NO_PARENT;
}
bool visited() const {
return m_visited;
}
void setVisited(bool visited) {
m_visited = visited;
}
};
class Tree {
private:
int m_root;
vector<Node> m_nodes;
public:
Tree(int root, const vector<Node>& nodes) : m_root(root), m_nodes(nodes) {
}
int root() const {
return m_root;
}
const vector<Node>& nodes() const {
return m_nodes;
}
const Node& getNode(int node) const {
return m_nodes[node];
}
Node& getNode(int node) {
return m_nodes[node];
}
void changeRoot(int newRootId) {
if (m_root == newRootId) return;
int nodeId = newRootId;
int oldParentNodeId = getNode(nodeId).parent();
while (nodeId != m_root) {
Node& node = getNode(nodeId);
const int parentNodeId = oldParentNodeId;
Node& parentNode = getNode(parentNodeId);
oldParentNodeId = parentNode.parent();
parentNode.setParent(nodeId);
parentNode.removeChild(nodeId);
node.addChild(parentNodeId);
nodeId = parentNodeId;
}
Node& newRoot = getNode(newRootId);
newRoot.setParent(Node::NO_PARENT);
m_root = newRootId;
}
static Tree make(const vector<int>& edges) {
vector<Node> nodes;
nodes.reserve(edges.size());
for (int i = 0; i < (int) edges.size(); i++) {
const Node node(i);
nodes.push_back(node);
}
int root = -1;
for (int i = 0; i < (int) edges.size(); i++) {
const int j = edges[i];
if (i != j) {
nodes[i].setParent(j);
nodes[j].addChild(i);
} else {
root = i;
}
}
if (root == -1) {
throw runtime_error("Invalid tree");
}
return Tree(root, nodes);
}
};
void removeNonLeaves(const Tree& tree, vector<int>& nodes) {
for (vector<int>::iterator it = nodes.begin(); it != nodes.end(); ) {
const Node& node = tree.getNode(*it);
if (!node.leaf()) {
it = nodes.erase(it);
} else {
++it;
}
}
}
vector<vector<int> > createLevels(const Tree& tree) {
vector<vector<int> > levels;
vector<int> level0; level0.push_back(tree.root());
levels.push_back(level0);
vector<int> currLevel;
while (! (*(levels.end() - 1)).empty() ) {
const vector<int>& prevLevel = *(levels.end() - 1);
for (vector<int>::const_iterator it = prevLevel.begin();
it != prevLevel.end(); ++it) {
const Node& node = tree.getNode(*it);
currLevel.insert(currLevel.begin(), node.children().begin(),
node.children().end());
}
levels.push_back(currLevel);
currLevel.clear();
}
levels.pop_back();
for (size_t i = 0; i < levels.size(); i++) {
removeNonLeaves(tree, levels[i]);
}
return levels;
}
int computeActualLevel(const Tree& tree, int nodeId) {
int result = 0;
while (nodeId != tree.root()) {
const Node& node = tree.getNode(nodeId);
if (!node.visited()) {
result++;
nodeId = node.parent();
} else {
break;
}
}
return result;
}
void visit(Tree& tree, int nodeId) {
while (nodeId != tree.root()) {
Node& node = tree.getNode(nodeId);
if (!node.visited()) {
node.setVisited(true);
nodeId = node.parent();
} else {
break;
}
}
}
#include <iostream>
vector<int> solution(int startNode, vector<int>& edges) {
Tree tree = Tree::make(edges);
tree.changeRoot(startNode);
vector<vector<int> > levels = createLevels(tree);
vector<int> result; result.push_back(startNode);
for (int i = levels.size() - 1; i >= 0; i--) {
vector<int>& level = levels[i];
sort(level.begin(), level.end());
for (vector<int>::iterator it = level.begin(); it != level.end(); ) {
const int nodeId = *it;
const int actualLevel = computeActualLevel(tree, nodeId);
if (actualLevel != i) {
levels[actualLevel].push_back(nodeId);
it = level.erase(it);
} else {
visit(tree, nodeId);
result.push_back(nodeId);
++it;
}
}
}
return result;
}
The solution obtained perfect score.