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