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.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Apply
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Roads and Libraries
  5. Discussions

Roads and Libraries

Problem
Submissions
Leaderboard
Discussions
Editorial

    You are viewing a single comment's thread. Return to all comments →

  • alexei_fedotkin
    6 months ago+ 2 comments

    C# is Power


    private static int Search(int node, bool[] visited, List<List<int>> nextNodes)
    {
        int citiesInGroup = 1;
        visited[node] = true;
    
        foreach (int item in nextNodes[node])
        {
            if (!visited[item])
                citiesInGroup += Search(item, visited, nextNodes);
        }
    
        return citiesInGroup;
    }
    
    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;
    
        long cost = 0;
        bool[] visited = new bool[n + 1];
        List<List<int>> nextNodes = new List<List<int>>(n + 1);
    
        for (int i = 0; i <= n; i++)
        {
            nextNodes.Add(new List<int>());
        }
    
        foreach (var cityPair in cities)
        {
            int indexFor0 = cityPair[0];
            int indexFor1 = cityPair[1];
            nextNodes[indexFor0].Add(indexFor1);
            nextNodes[indexFor1].Add(indexFor0);
        }
    
        for (int i = 1; i <= n; i++)
        {
            if (!visited[i])
            {
                int citiesInGroup = Search(i, visited, nextNodes);
                cost += c_lib + (long)(citiesInGroup - 1) * c_road;
            }
        }
    
        return cost;
    }
    
    1|
    Permalink
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy