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. Prepare
  2. Algorithms
  3. Graph Theory
  4. Roads and Libraries
  5. Discussions

Roads and Libraries

Sort by

recency

|

889 Discussions

|

  • muhammed_aly16
     + 0 comments

    I solved it using DSU - wikipedia:

    class DSU {
private:
    int nodesCount;
    int parent[100001];
    int size[100001];
public:
    DSU(int n) {
        nodesCount = n;
        for (int i = 1 ; i <= n ; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }
    
    int findParent(int node) {
        return parent[node] = (parent[node] == node)? node : findParent(parent[node]);
    }
    
    bool join(int u, int v) {
        u = findParent(u);
        v = findParent(v);
        
        if (u == v) return false;
        
        if (size[v] > size[u]) {
            swap(u, v);
        }
        
        size[u] += size[v];
        parent[v] = u;
        return true;
    }
    
    int getUnionsCount() {
        int ret = 0;
        for (int i = 1 ; i <= nodesCount ; i++) {
            int p = findParent(i);
            if (p == i) {
                ret++;
            }
        }
        return ret;
    }
};

long roadsAndLibraries(int n, int c_lib, int c_road, vector<vector<int>> cities) {
    DSU dsu(n);
    int roads = 0;
    for (auto city : cities) {
        if (dsu.join(city[0], city[1])) {
            roads++;
        }
    }

    return min(1L * roads * c_road + 1L * dsu.getUnionsCount() * c_lib, 1L * c_lib * n);
}

  • yumingjing7
     + 0 comments
        public static long roadsAndLibraries(int n, int c_lib, int c_road, List<List<int>> cities)
    {
        if (c_lib <= c_road || cities == null ||cities.Count() == 0) return (long)(long)(n) * (long)(c_lib);
        Dictionary<int, List<int>> grap = new Dictionary<int,List<int>>();
        foreach(var c in cities)
        {
            int from = c[0];
            int to = c[1];
            if(!grap.ContainsKey(from)) grap[from] = new();
            if(!grap.ContainsKey(to)) grap[to] = new();
            grap[from].Add(to);
            grap[to].Add(from);
        }
        long res = 0;
        int[] seen = new int[n+1];
        long clusters = 0;
        for(int i = 1; i <=n ; i++)
        {
            if(seen[i] == 1) continue;
            seen[i] = 1;
            clusters++;
            Queue<int> q  = new Queue<int>();
            q.Enqueue(i);
            while(q.Count() > 0)
            {
                var front = q.Dequeue();
                if(grap.ContainsKey(front)){
                    foreach(var entry in grap[front])
                    {
                        if(seen[entry] == 0) {
                            q.Enqueue(entry);
                            seen[entry] = 1;
                        }
                    }
                }
            }
        }
        res = (long)(clusters) * (long)(c_lib) + (long)(n-clusters)* (long)(c_road);
        return res;
    }

  • villeyvince
     + 0 comments

    It’s interesting how breaking the tree into components becomes much clearer once you focus on counting the subtrees and checking where an even split is possible. Your explanation helps simplify the logic behind the cuts, especially for anyone struggling with the recursive approach. Sometimes stepping back and viewing the structure as smaller manageable parts makes the whole problem feel less overwhelming. By the way, coordinating complex tasks like this reminds me of organizing group travel—using a Part bus setup can make things run just as smoothly.

  • narekhovakimyan2
     + 0 comments

    If you get WA on 6 hidden tests try this:

    1ll*n*c_lib instead of n*c_lib*1ll or n*c_lib (same for 1ll * c_lib + (comp-1) * c_road)

  • huypn12
     + 0 comments

    I spent quite some time to figure out why my solution didnt pass the 7 heavy input test cases. It turned out that since i tried to convert the edge list to adjacency matrix, the test ran out of memory. So instead of adjacency matrix, i use std::map as adjacency list. map> toAdjList(int n, vector> cities) { map> result = {}; for (const auto &ct : cities) { int a = ct[0]; int b = ct[1]; if (result.find(a) == result.end()) { result[a] = vector(); } result[a].push_back(b); if (result.find(b) == result.end()) { result[b] = vector(); } result[b].push_back(a); }

    return result;

    }

    long roadsAndLibraries(int n, int c_lib, int c_road, vector> cities) { if (n == 0) return 0; if (n == 1) return c_lib;

    vector<bool> visited(n + 1, 0);
map<int, vector<int>> adjList = toAdjList(n, cities);

long totalCost = 0;
queue<int> q;
std::cout << "processig " << n << std::endl;    
for (int i = 1; i <= n; i++) {
    if (visited[i]) continue;

    q.push(i);
    visited[i] = true;
    long nodeCount = 1;
    while (!q.empty()) {
        int currNode = q.front();
        q.pop();
        for (const auto &adjNode : adjList[currNode]) {
            if (!visited[adjNode]) {
                q.push(adjNode);
                visited[adjNode] = true;
                nodeCount++;
            }
        }
    }
    totalCost += std::min(nodeCount * c_lib, c_lib + (nodeCount - 1) * c_road);
}

return totalCost;

    } `