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;
    }
};

Online OA1: Minimum Strongly Connected Network

Q: Minimum Strongly Connected Network

A group of software engineers want to develop an algorithm for finding strongly connected groups among members of a social networking site. A group of people are considered to be strongly connected if each person knows each other person within the group.

Given M nodes and N edges develop an algorithm that determines the minimum size of the largest strongly connected group.

Constraints:
1 <= N <= 100000
0 <= M <= 10000
0 <= M <= N*(N-1)/2


Notes:

This question seems one of the popular OA questions . In this link below,

http://canyon289.github.io/MinStrongNetwork.html#click-to-start-search

you can find a complete description of this question, plus some examples and ideas (but it seems that the idea on this page is not a good one to solve this problem.)

Let us begin with some small cases:

when N = 1, it always is 1;

when N = 2, it is 1 when M <1, and it is 2 when M>=1;

when N = 3, it is 1 when M<1, and it is 2 when M>=1 and M<3, and it is 3 when M>=3;

when N = 4, it is 1 when M<1, and it is 2 when (which is the key part), ... and it is 4 when M>=6;


Now let us focus on the key part:

when N = 4, if we link the 4 nodes into a circle with 4 edges (M=4), then it is still 2. If we add another edge (M=5), then it becomes 3; then add another one (M=6), they are fully connected.

Thus,
when N = 4, it is 1 when M<1, and it is 2 when M>=1 and M<=4, and it is 3 when M=5, and it is 4 when M>= 6.

So it seems that one way to solve this problem is that we just need to form a circle first, and then add more edges with the constrain that do not increase the size of any strongly connected components (scc) until have to. And this is essentially the idea in that link cited above. But it seems have some problems. Firstly, is this idea correct?

Let us look at the case when N = 5.

If we follow the idea in the link, we form a circle with 5 nodes which gives us 5 edges. Now we cannot add one more edge since it will always make the minimum size of the largest scc (lscc) to become 3.

However, if we form a circle with 4 nodes first which gives 4 edges, and we have last node unconnected. In order to better illustrate the idea, let us label the node from 1 to 5, and 1 to 4 are connected forming a circle consecutively. So we then can connect the 5th node with 1 and 3 forming another 2 edges without increase the minimum size of the lscc. (or connect 2 and 4 nodes, which gives the same results.)

But now we can have 6 edges with 5 nodes with the minimum size of lscc of 2!!!

So the above greedy way does not work.

Now let's try something different:

The answer to this question apparently is in a range: the min = 1, and the max = N. And it is asking for the minimum size of the lscc, so it can naturally lead the very fundamental binary search idea.

Now let's set Left = 1, Right = N, then Mid = Left + (Right - Left)/2. If we cannot connect the N nodes in such a way that the minimum size of the lscc is not larger than Mid with M edges, or there are more edges than needed and we have to increase Mid in order to run up all the M edges, then current Mid is too small (or invalid), and we can update Left = Mid + 1; otherwise, we can update Right = Mid.

In this way, we can eventually find the correct value which is Left == Right.

So now the key question becomes: given N nodes and the lscc is Mid, what is the maximum number of edges that can be added onto? And we need the answer to this question in the above binary searching.

Again let's start with small cases:

when  N = 4, and Mid  = 2. We firstly fully connect 1 to 2, and 3 to 4, to form two scc with a size of Mid = 2. Now we have 2 edges. Next, we can connect 1 to 3, and 2 to 4. (or 1 to 4, and 2 to 3). So the maximum is 4 edges;

when N = 4, and Mid = 3. We can firstly fully connect 1, 2, 3 to form a scc with a size of 3, then connect 4 to 1, and 4 to 2. (or 4 to 1, and 4 to 3; or 4 to 2, and 4 to 3). So one of the key observation is that 4 cannot connect all the nodes in a scc, otherwise it will increase the size of scc by 1. So the maximum is 5 edges.

It seem still not enough to derive the result that can be applied to all the cases. Let us continue,

when N = 5, and Mid = 2. Follow the similar idea of when N = 4, we can firstly form 2 scc's by fully connect 1 to 2, and 3 to 4, respectively. Next, we can connect 1 to 3 and 2 to 4. The last step is new: we have a unconnected node 5. After some trails and errors, it is found that we can connect 5 to 1, and 5 to 3. (or 5 to 1, and 5 to 4, or 5 to 2, and 5 to 3, or 5 to 2, and 5 to 4. The key is the same, 5 cannot connect all the nodes in a scc). So the maximum is 6 edges.

It is time to make some summaries:

1): we form as many scc's as possible with a size of Mid; the total number of the scc edges is easy to calculate

2): we need to calculate all the possible connections between every two scc's with a size of Mid;

3): we need to take care of the remainders whose size is smaller than Mid (it turns out later that this is essentially the same as 2)).

We need to figure out how many edges we can place between nodes.

For 1): the answer is straightforward: (N/Mid) * (Mid*(Mid-1)/2) = num_scc *  edge_num_scc;

Step 2) seems not that easy. Let start again with some example, when N = 6, and Mid = 3. So we have 2 scc's with a size of 3. Let say 1, 2, 3 are in a scc, and 4, 5, 6 in the other scc. Now we can connect 1 to 4 and 5 (2 more edges) but not 6 (or it will increase the size of scc); then 2 to 5 and 6, then 3 to 6 and 4. The total maximum connections between 2 scc's with the same size of Mid is Mid * (Mid - 1).

But we may have more than 2 scc's. For example, when N = 9 and Mid = 3. In this case, every 2 scc's can be connected in the similar way, which gives a factor of  F = (N/Mid)*(N/Mid - 1)/2. Thus, the total maximum number of edges for step 2 is: F * Mid * (Mid - 1) = (N/Mid)*(N/Mid - 1)/2 * Mid * (Mid - 1).

Before we move on to step 3), let look an interesting question first. What are the maximum number of connections between 2 scc's with different sizes, without increasing the minimum size of lscc?

Let say one scc has a size of Mid, and the other is R which is smaller than Mid. Similar to the above case of 2 scc's with the same size, every node in the second scc can connect (Mid - 1) nodes in the first one. Thus, the total number of edges is R * (Mid - 1).

If there are (N/Mid)  scc's, then the total number of edges is (N/Mid) * R * (Mid - 1), which is one part of the answer to the step 3).

What is still missing?

If we have more than 1 node in the remaining. For example, Mid = 4, R = 3. The 3 nodes can form a scc first. So this part will give R* (R - 1)/2 edges.

Thus the final answer to step 3) is R* (R - 1)/2 + (N/Mid) * R * (Mid - 1).

The total number of edges are the sum the all three steps.

We are done. And the next step is coding.


Please see the code below:

#include <iostream>
#include <vector>

using namespace std;

int minMax_scg(int &m, int &n);
int maxEdge(int &m, int &max_scg);

int main() {
    int num_node = 100, num_edge = 4900;
    return minMax_scg(num_node, num_edge);
}

int minMax_scg(int &m, int &n) {
    int left = 1, right = m;
    while(left < right) {
        int mid = left + (right - left) / 2;
        if(maxEdge(m, mid) < n) left = mid + 1;
        else right = mid;
    }
    cout<<"The minimum size of the largest scc = " <<left<<endl;
    return left;
}

int maxEdge(int &m, int &max_scg) {
    int num_scg_compo = m / max_scg;
    int remainer = m % max_scg;
    int a = max_scg, b = num_scg_compo, c = remainer;
    int maxE = b*a*(a-1)/2 + b*(b-1)/2*a*(a-1) + c*(c-1)/2 + b*c*(a-1);
    cout<<"num_node = "<<m<<" max_scg = "<<max_scg<<" maxNumEdge = "<<maxE<<endl;
    return maxE;
} 

Please leave any comment if you find some incorrect places or improvements. Any discussion is also welcome! 

PS: after finishing the writing, I feel that the there may be existed formula to calculate the maximum number of edges for a un-directed graph with N nodes and the lscc of K (K <= N). Please let me know if you find this somewhere. Thanks.

Leetcode 1042: Flower Planting With No Adjacent

https://leetcode.com/problems/flower-planting-with-no-adjacent/description/

Note:

• 1 <= N <= 10000
• 0 <= paths.size <= 20000
• No garden has 4 or more paths coming into or leaving it.
• It is guaranteed an answer exists.

Notes:

This question seems not easy, but actually it can be solved in a greedy way.

The first step is to build a graph with adjacent elements. Then is the key: for each element i or the ith garden, we need to check its neighbors (less than 4). If they have been planned with flowers, we cannot plan that kind of flower in ith. Otherwise, we can.

See the code below:

class Solution {
public:
    vector<int> gardenNoAdj(int N, vector<vector<int>>& paths) {
        vector<int> res(N, 0);
        vector<vector<int>> g(N);
        for(auto &a : paths){
            g[a[0]-1].push_back(a[1]-1);
            g[a[1]-1].push_back(a[0]-1);
        }
        for(int i=0; i<N; ++i){
            vector<int> used(5, 0);
            for(auto &a : g[i]) used[res[a]] = 1;//if used, label as 1;
            for(int fl = 1; fl <5; ++fl) {
                if(!used[fl]) {res[i] = fl; break;}
            }
        }
        return res;
    }
};

Leetcode 277: Find the Celebrity

https://leetcode.com › problems › find-the-celebrity

Notes:

One way to think about this question is that: for each pair of (i, j), once we find i know j, or j doesn't know i, then i is not a celebrity. Otherwise, if i doesn't know j, but j knows i. Then j is not celebrity neither. See the code below:

bool knows(int a, int b);

class Solution {
public:
    int findCelebrity(int n) {
        vector<bool> candidate(n, true);//memorize the results
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {//compare i with all the rest
                if (candidate[i] && i != j) {
                    if (knows(i, j) || !knows(j, i)) {
                        candidate[i] = false;
                        break;
                    } else {
                        candidate[j] = false;
                    }
                }
            }
            if (candidate[i]) return i;
        }
        return -1;
    }
};