We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Roads and Libraries
  2. Discussions

Roads and Libraries

  • fencullen
     + 0 comments

    C# solution using Union-Find Algorithm explained here: https://www.geeksforgeeks.org/introduction-to-disjoint-set-data-structure-or-union-find-algorithm/

    class Result
{
    // Uses the Union-Find algorithm to find the number of connected components.
    public static long roadsAndLibraries(int n, int c_lib, int c_road, List<List<int>> cities)
    {
        if (c_lib < c_road)
        {
            return (long)c_lib * n;
        }
        
        int[] parents = new int[n+1]; // n+1 because cities are 1-indexed.
        
        // Init with each node as its own parent.
        for (int i = 0; i <= n; i++)
        {
            parents[i] = i;
        }
        
        foreach (List<int> edge in cities)
        {
            Union(edge[0], edge[1], parents);
        }
        
        // Final round up. Now parents points to the root of each component.
        for (int i = 0; i <= n; i++)
        {
            parents[i] = Find(i, parents);
        }
        
        List<int> parentsList = parents.ToList();
        long components = parentsList.Distinct().LongCount() - 1; // -1 because parents[0] doesn't really exist.
        long edges = n - components;
        
        return (components * c_lib) + (edges * c_road);
    }