Diameter of a tree and topological sort

Explanation

  • use the diameter of a tree template to solve it
  • use the topological sort to solve this one.

Using diameter of a tree

  1. The result at most have two nodes. 1) when the longest path’s length is odd, we have one node as res. 2) when the longest path’s lenght is even, we have two nodes.
  2. The result nodes can only exist in the longest path.
  3. The longest path is the diameter of the tree
  4. The diameter of a tree is a template problem and it can be solved by using two BFSs.
  1. Two bfs to find the diameter
  2. Use DFS to find the middle points of the longest path from the start node and end node of the longest path.

C++ code

class Solution {
public:
int node;
void bfs(vector<vector<int>>& graph, int n, int firstnode, int& lastnode, int& longestPathLen){
vector<int> current_level = {firstnode};
longestPathLen = 0;
vector<int> seen(n, 0);
seen[firstnode] = 1;
while (!current_level.empty()){
vector<int> next_level;
for (auto & node: current_level){
for (auto & nei: graph[node]){
if (seen[nei])continue;
seen[nei] = 1;
next_level.push_back(nei);
lastnode = nei;
}
}
current_level = next_level;
if(!current_level.empty())longestPathLen++;
}
}
void dfs(vector<vector<int>>& graph, int i, int curr, int target_depth, unordered_set<int>&s, vector<int>& seen){

for (auto & nei: graph[i]){
if (seen[nei] || curr > target_depth) continue;
seen[nei] = 1;
if (curr + 1 == target_depth){
s.insert(nei);
}
dfs(graph, nei, curr + 1, target_depth, s, seen);
}
}
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
if (n == 1) return {0};
vector<vector<int>> graph(n + 1);
for (auto & e: edges){
graph[e[0]].push_back(e[1]);
graph[e[1]].push_back(e[0]);
}
// find the diameter of a tree
int firstnode = 0, lastnode = 0, longestPathLen = 0;
bfs(graph, n, firstnode, lastnode, longestPathLen);
firstnode = lastnode;
longestPathLen = 0;
bfs(graph, n, firstnode, lastnode, longestPathLen);


// find the nodes which has a distance of half of the longest path to the startnode and endnode
// if the path length is odd, we need find half lenght and half length + 1
int depth = longestPathLen / 2;
unordered_set<int> s1, s2;
vector<int> seen(n, 0);
dfs(graph, firstnode, 0, depth, s1, seen);
seen.assign(n, 0);
dfs(graph, lastnode, 0, depth, s2, seen);
if (longestPathLen %2 != 0){
depth ++;
seen.assign(n, 0);
dfs(graph, firstnode, 0, depth, s1, seen);
seen.assign(n, 0);
dfs(graph, lastnode, 0, depth, s2, seen);
}

vector<int> ret;
for (auto& x: s2){
if (s1.find(x) != s1.end()){
ret.push_back(x);
}
}
return ret;

}
};

Using topological sort to solve this problem

IMAGE IS FROM HERE

C++

const int N = 2e4 + 10;
int indegree[N];
// indicate whether the node is explored or not
int explored[N];
class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
vector<int> ret;
memset(indegree, 0, sizeof indegree);
memset(explored, 0, sizeof explored);
// build the graph
vector<vector<int>> graph(n);
for (auto &e: edges)
{
indegree[e[0]]++;indegree[e[1]]++;
graph[e[0]].push_back(e[1]);
graph[e[1]].push_back(e[0]);
}
// explore the graph by using a topological way.
// Attention, as the graph is bidirectional,
// we should explore the indegree with 1 nodes.
int explored_sofa = 0;
vector<int> current_level;
for (int i = 0; i < n; ++i)
if(indegree[i] == 1)
current_level.push_back(i);
// when the unexploed nodes is 1 or 2, break.
while (n - explored_sofa > 2)
{
vector<int> next_level;
for (auto & node: current_level)
{
explored[node] = 1;
explored_sofa++;
for (auto & nei: graph[node])
{
if (--indegree[nei] == 1)
next_level.push_back(nei);
}
}
current_level = next_level;
}
// the unexplored nodes will be our result.
for (int i = 0; i < n; ++i)if(!explored[i])ret.push_back(i);
return ret;
}
};

--

--

--

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Docker Log Management Using EFK Stack

Un-Shorten your urls.

Developer Incentives in Sia

Build and run your sample app with Docker (demo)

Elevated access for dotnet commands

Handling Deadlocks in Snowflake

Best Practices for Kubernetes Network Policies

The worst abuse of the C preprocessor (Jim Hague 1986)

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi

More from Medium

Union Find Disjoint Set: The most underrated data structure

Starting Data Structures and Algorithms

Multithreading environment and Concurrency Issues

What actually is “Probabilistic record linkage”