Leetcode 1245: Tree Diameter

https://leetcode.com/contest/biweekly-contest-12/problems/tree-diameter/

Notes:

This is a very good question. So apparently, both DFS and BFS can be applied to solve this problem.

The naive DFS idea is we can start with any node, which is as the root of the tree, then we need to find the top 2 longest path down to the leaves. The sum of the two longest path should be the longest path. One detail is that we need to remember the prev-node, to reduce redundant traversal. The time complexity is O(N*N).

One BFS idea is very clear: start with any node A, then find the furthest node from A, call it B; then start with Node B, find the furthest Node C. Then the distance between B and C is the distance. So the time complexity is O(2*N) due to two traversals.

However, here I want to share another BFS method: from the edges to the roots, which only requires one traversal.

We need to count the indgrees of each node. Then we start with all the nodes with indegree of 1. Then layer-by-layer approaches the roots.

There may be one final node as the roots, or two nodes. If only node left, we just need to double number of layers in the BFS; otherwise, we need to add 1.

Apparently, we assume there is no loop existing in this question.

See the code below:

class Solution {
public:
    int treeDiameter(vector<vector<int>>& edges) {
        unordered_map<int, vector<int>> gh;
        unordered_map<int, int> ind;
        for(auto &a : edges) {
            gh[a[0]].push_back(a[1]);
            gh[a[1]].push_back(a[0]);
            ++ind[a[0]];
            ++ind[a[1]];
        }
        queue<int> q;
        for(auto &a : ind) {
            if(a.second == 1) {
                q.push(a.first);
                --ind[a.first];
            }
        }
        int step = 0, last = 0;
        while(q.size()) {
            int k = q.size();
            for(int i=0; i<k; ++i) {
                auto t = q.front();
                q.pop();
                for(auto &a : gh[t]) {
                    --ind[a];
                    if(ind[a] == 1) q.push(a);
                }
            }
            ++step;
            if(q.empty() && k == 2) last = 1;
        }
        return (step-1)*2 + last;
    }
};

Leetcode 1203: Sort Items by Groups Respecting Dependencies

https://leetcode.com/problems/sort-items-by-groups-respecting-dependencies/description/

Notes:

This question is a hard question, due to its complicated logic. It is mainly about the topological sort algorithm.

First of all, there are more than one groups. And we need to run a topological sort to all the groups, to make sure they can be arranged;

Second, inside each group, we also need to run a topological sort, to make sure that they also can be arranged in the required orders.

The topological sort is a typical algorithm, which usually requires the indgrees of each note. Firstly we will start the sort with the node having a indgree of 0 which means there is no prerequisite. During visiting or sorting, we can gradually decrease the indgree of the unvisited node when their pre-nodes are visited. Once its indegree becomes 0, it can ready to be visited.

Please check the code below:

class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        vector<int> res;
        unordered_map<int, set<int>> gs;//group structures;
        unordered_map<int, set<int>> group_graph;//group relations
        unordered_map<int, int> group_indgree;//group indgrees;
        unordered_map<int, set<int>> memb_graph;//member relations;
        unordered_map<int, int> memb_indgree;//memeber indgree;
       
        int num_group = m;
        for(int i=0; i<group.size(); ++i) {
            if(group[i] == -1) {//listed as one unique group
                group[i] = num_group++;
            }
            gs[group[i]].insert(i);
        }
       
        for(int to=0; to<beforeItems.size(); ++to) {
            int to_group = group[to];
            for(auto &from : beforeItems[to]) {
                int from_group = group[from];
                if(from_group == to_group) {//belong to the same sub-group;
                    if(!memb_graph[from].count(to)) {
                     memb_graph[from].insert(to);
                     ++memb_indgree[to];
      }
                }
                else {
      if(!group_graph[from_group].count(to_group)) {
                     group_graph[from_group].insert(to_group);
                     ++group_indgree[to_group];
      }
                }
            }
        }

        vector<int> group_res;
        queue<int> q;
        for(int i=0; i<num_group; ++i) {
            if(group_indgree[i] == 0) {
                q.push(i);
                group_res.push_back(i);
            }
        }
        while(q.size()) {
            int t = q.front();
            q.pop();
            for(auto &a : group_graph[t]) {
                if(group_indgree[a] == 0) continue;
                --group_indgree[a];
                if(group_indgree[a] == 0) {
                    q.push(a);
                    group_res.push_back(a);
                }
            }
        }
        if(group_res.size() != num_group) return {};
      
        for(auto &a : group_res) {//check each group
            int ct = 0;
            for(auto &b : gs[a]) {
                if(memb_indgree[b] == 0) {
                    q.push(b);
                    res.push_back(b);
                    ++ct;
                }
            }
            while(q.size()) {
                auto t = q.front();
                q.pop();
                for(auto &c : memb_graph[t]) {
                    if(memb_indgree[c] == 0) continue;
                    --memb_indgree[c];
                    if(memb_indgree[c] == 0) {
                        q.push(c);
                        res.push_back(c);
                        ++ct;
                    }
                }
            }
            if(ct != gs[a].size()) return {};
        }

        return res;
    }
};