Introduction

Topological sorting is a pretty elementary yet powerful algorithm. The idea behind it reminds me of some elements of ‘homotopy theory’ and is perhaps one of the most beautiful graph algorithms on my personal list. Unfortunately, many related coding challenges require just a straightforward implementation without much variation, which is why I was quite happy to encounter 3203. Find Minimum Diameter After Merging Two Trees.

The challenge itself is pretty straightforward: we have two trees and need to find the minimum diameter among all trees obtained by connecting them with an edge. The first naive approach is to check all possible trees and compute their diameters, for instance, by running a two-pass BFS(similar to what we did here). However, the input conditions 1 <= n, m <= 105 imply that this naive approach is impractical as we get roughly O(n*m*(n + m)) operations.

The Algorithm

Let’s consider the diameter of a ‘merged’ graph. It either lies within the first graph, the second graph, or spans both graphs via the added edge. The diameters of the first two cases depend only on the input graphs and remain constant, meaning we only need to minimize the third case. To achieve this, we need to independently select a ‘mid’ vertex in each graph that minimizes the total distance to all other vertices within its respective graph.

How do we pick such a vertex? Computing all distances using an algorithm like Floyd-Warshall is again infeasible, so we need a more efficient approach. Obviously, it is not wise to pick a leaf (unless the graph consists of just two vertices)…This gives us a crucial hint: we can iteratively erase all the leaves in the current step and repeat the process on the remaining graph…This is exactly the same idea as in the topological sorting! At the end of this process, we obtain a vertex along with the distance required to visit every other node from it(amount of times we applied the operation).

So, to get the final result, we simply compare the two given diameters with the sum of the two distances obtained from the concatenation of the graphs plus one.

The implementation

Here is the code in C# that implements the above idea:

public class Solution {
    public int MinimumDiameterAfterMerge(int[][] edges1, int[][] edges2) 
    {
        var first = BuildGraph(edges1);
        var second = BuildGraph(edges2);

        var firstDiameter = FindDiameter(first);
        var secondDiameter = FindDiameter(second);

        return Math.Max(Math.Max(firstDiameter, secondDiameter), 
                            TopologicalSorting(first) + TopologicalSorting(second) + 1);        
    }

    public int TopologicalSorting(Dictionary<int, HashSet<int>> graph)
    {
        var toVisit = new HashSet<int>();

        foreach(var (vertex, edges) in graph )
        {
            if(edges.Count == 1)
            {
                toVisit.Add(vertex);
            }
        }

        var count = 0;

        while(toVisit.Count > 0)
        {
            var newToVisit = new HashSet<int>();
            foreach(var candidate in toVisit)
            {
                if(graph.ContainsKey(candidate))
                {
                    foreach(var newCandidate in graph[candidate])
                    {
                        graph[newCandidate].Remove(candidate);
                        if(graph[newCandidate].Count == 1)
                        {
                            newToVisit.Add(newCandidate);
                        }
                        if(graph[newCandidate].Count == 0)
                        {
                            newToVisit.Remove(newCandidate);
                        }
                    }
                }
                graph.Remove(candidate);
            }

            toVisit = newToVisit;
            ++count;
        } 

        return count;
    }

    public int FindDiameter(Dictionary<int, HashSet<int>> graph)
    {
        var (first, maxDistance) = BFS(graph, BFS(graph, graph.Keys.First()).Item1);

        return maxDistance;
    }

    public Dictionary<int, HashSet<int>> BuildGraph(int[][] edges)
    {
        var graph = new Dictionary<int, HashSet<int>>();
        var edgesCount = 0;
        var n = edges.Length + 1;

        for(int i = 0; i < n; ++i)
        {
            graph.TryAdd(i, new HashSet<int>());
        }

        foreach(var edge in edges)
        {
            var start = edge[0];
            var end = edge[1];

            graph.TryAdd(start, new HashSet<int>());
            graph[start].Add(end);

            graph.TryAdd(end, new HashSet<int>());
            graph[end].Add(start);
        }

        return graph;
    }

    public (int, int) BFS(Dictionary<int, HashSet<int>> graph, int start)
    {
        var toVisit = new HashSet<int>();
        toVisit.Add(start);
        var visited = new HashSet<int>();
        
        var count = 0;
        var lastIndex = start;

        while(toVisit.Count > 0)
        {
            ++count;
            var newToVisit = new HashSet<int>();
            foreach(var candidate in toVisit)
            {
                visited.Add(candidate);
                if(graph.ContainsKey(candidate))
                {
                    foreach(var newCandidate in graph[candidate])
                    {
                        if(!visited.Contains(newCandidate))
                        {
                            newToVisit.Add(newCandidate);
                            lastIndex = newCandidate;
                        }
                    }
                }
            }
            toVisit = newToVisit;
        }

        return (lastIndex, count - 1);
    }
}