Editing 2021 Dec Silver Problem 2 Connecting Two Barns

== Official Problem Statement ==

[http://www.usaco.org/index.php?page=viewproblem2&cpid=1159 Connecting Two Barns]

== Problem ==

Given a set of barns with some connected by existing roads, and barns are numbered in a sequence, add two new roads to ensure that there is a path from barn 1 to the last barn (N). The cost of constructing a road between two barns is the square of the absolute difference of their numbers. We need to find the minimum cost.

== Solution ==

Solution:

* Connected Components: First, we need to identify the connected components in the graph. A connected component is a maximal group of vertices where each pair of vertices is connected by a path. In the code, we use a Depth-First Search (DFS) to compute these connected components.

* Calculating Minimum Costs: Once we have the connected components, we consider two main cases:
** Add an edge directly from the connected component containing barn 1 to the component containing barn N.
** Pick an intermediate component, add one edge from it to the component containing barn 1, and another edge from it to the component containing barn N.

In both cases, the task reduces to finding the minimum cost of connecting two components. We do this by iterating over the barns in a component and considering the cost of adding an edge to every other barn, picking the minimum cost.

This approach, however, can still be slow if the number of barns is large.

* Optimizing the Costs: We optimize by realizing that for a given barn and a given connected component we want to connect it to, we only care about the smallest integer in the connected component greater than it, and the largest integer in the component less than it. We calculate this efficiently by maintaining pairs of indices and adding edges from vertices in increasing order.

The code first reads the number of barns (n) and the number of existing roads (m), and builds the adjacency list representing the existing connections. Then it computes the connected components, and for each component, it calculates the minimum cost of adding a road from a barn in that component to barn 1 and to barn N. It keeps track of the minimum cost encountered. If barn 1 and barn N are in the same connected component, it outputs 0 since no new roads are needed. Otherwise, it outputs the minimum cost it has computed.

In conclusion, this solution leverages the understanding of connected components and cost optimization to solve the problem in a computationally efficient manner.

== Code ==


=== C++ ===

<pre>
#include <bits/stdc++.h>
using namespace std;

// helper function to perform a depth-first search (DFS) on the graph
void dfs(unordered_map<int, vector<int>>& graph, vector<int>& component, int currentNode, int id) {
    // iterate over all adjacent nodes
    for (auto adjacentNode : graph[currentNode]) {
        if (component[adjacentNode] != id) {
            component[adjacentNode] = id;
            dfs(graph, component, adjacentNode, id);
        }
    }
}

void solve() {
    int n, m;
    cin >> n >> m;

    unordered_map<int, vector<int>> graph;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    // initialize each node to be its own component
    vector<int> component(n);
    iota(component.begin(), component.end(), 0);

    // perform DFS to find all connected components
    for (int i = 0; i < n; i++) {
        if (component[i] == i) {
            dfs(graph, component, i, i);
        }
    }

    // group nodes by their components
    unordered_map<int, vector<int>> components;
    for (int i = 0; i < n; i++) {
        components[component[i]].push_back(i);
    }

    // if the first and last barn are already connected, output 0
    if (component[0] == component[n - 1]) {
        cout << 0 << endl;
        return;
    }

    // otherwise, calculate the minimum cost to connect them
    vector<long long> srcCost(n, 1e9);
    vector<long long> dstCost(n, 1e9);

    int srcIdx = 0;
    int dstIdx = 0;
    for (int i = 0; i < n; i++) {
        while (srcIdx < components[component[0]].size()) {
            srcCost[component[i]] = min(srcCost[component[i]], (long long)abs(i - components[component[0]][srcIdx]));
            if (components[component[0]][srcIdx] < i) srcIdx++;
            else break;
        }
        if (srcIdx) srcIdx--;

        while (dstIdx < components[component[n - 1]].size()) {
            dstCost[component[i]] = min(dstCost[component[i]], (long long)abs(i - components[component[n - 1]][dstIdx]));
            if (components[component[n - 1]][dstIdx] < i) dstIdx++;
            else break;
        }
        if (dstIdx) dstIdx--;
    }

    // find the minimum cost among all nodes
    long long minCost = 1e18;
    for (int i = 0; i < n; i++) {
        minCost = min(minCost, srcCost[i] * srcCost[i] + dstCost[i] * dstCost[i]);
    }

    cout << minCost << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}
</pre>


=== Java ===

<pre>
import java.util.*;
import java.io.*;

public class Main {
    static Map<Integer, ArrayList<Integer>> graph = new HashMap<>();
    static int[] components;
    static ArrayList<Integer>[] componentToVertices;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        while (t-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            graph.clear();
            for (int i = 0; i < n; i++) {
                graph.put(i, new ArrayList<>());
            }

            for (int i = 0; i < m; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken()) - 1;
                int b = Integer.parseInt(st.nextToken()) - 1;
                graph.get(a).add(b);
                graph.get(b).add(a);
            }

            components = new int[n];
            for (int i = 0; i < n; i++) {
                components[i] = i;
            }

            for (int i = 0; i < n; i++) {
                if (components[i] == i) {
                    dfs(i, i);
                }
            }

            componentToVertices = new ArrayList[n];
            for (int i = 0; i < n; i++) {
                componentToVertices[i] = new ArrayList<>();
            }

            for (int i = 0; i < n; i++) {
                componentToVertices[components[i]].add(i);
            }

            if (components[0] == components[n - 1]) {
                System.out.println(0);
                continue;
            }

            long[] srcCost = new long[n];
            long[] dstCost = new long[n];
            Arrays.fill(srcCost, (long)1e9);
            Arrays.fill(dstCost, (long)1e9);

            int srcIdx = 0, dstIdx = 0;

            for (int i = 0; i < n; i++) {
                while (srcIdx < componentToVertices[components[0]].size() && componentToVertices[components[0]].get(srcIdx) <= i) {
                    srcIdx++;
                }
                if (srcIdx != 0) srcIdx--;
                srcCost[components[i]] = Math.min(srcCost[components[i]], (long)Math.abs(i - componentToVertices[components[0]].get(srcIdx)));

                while (dstIdx < componentToVertices[components[n - 1]].size() && componentToVertices[components[n - 1]].get(dstIdx) <= i) {
                    dstIdx++;
                }
                if (dstIdx != 0) dstIdx--;
                dstCost[components[i]] = Math.min(dstCost[components[i]], (long)Math.abs(i - componentToVertices[components[n - 1]].get(dstIdx)));
            }

            long minCost = (long)1e18;
            for (int i = 0; i < n; i++) {
                minCost = Math.min(minCost, srcCost[i] * srcCost[i] + dstCost[i] * dstCost[i]);
            }
            System.out.println(minCost);
        }
    }

    public static void dfs(int node, int id) {
        for (int child : graph.get(node)) {
            if (components[child] != id) {
                components[child] = id;
                dfs(child, id);
            }
        }
    }
}
</pre>


=== Python ===

<pre>
from collections import defaultdict
import sys
input = sys.stdin.readline

def dfs(node, id):
    for child in graph[node]:
        if components[child] != id:
            components[child] = id
            dfs(child, id)

def solve():
    n, m = map(int,input().split())
    global graph
    graph = defaultdict(list)

    for _ in range(m):
        a, b = map(int,input().split())
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)

    global components
    components = list(range(n))

    for i in range(n):
        if components[i] == i:
            dfs(i, i)

    componentToVertices = defaultdict(list)

    for i in range(n):
        componentToVertices[components[i]].append(i)

    if components[0] == components[n - 1]:
        print(0)
        return

    srcCost = [1e9]*n
    dstCost = [1e9]*n

    srcIdx, dstIdx = 0, 0

    for i in range(n):
        while srcIdx < len(componentToVertices[components[0]]) and componentToVertices[components[0]][srcIdx] <= i:
            srcIdx += 1
        if srcIdx != 0:
            srcIdx -= 1
        srcCost[components[i]] = min(srcCost[components[i]], abs(i - componentToVertices[components[0]][srcIdx]))

        while dstIdx < len(componentToVertices[components[n - 1]]) and componentToVertices[components[n - 1]][dstIdx] <= i:
            dstIdx += 1
        if dstIdx != 0:
            dstIdx -= 1
        dstCost[components[i]] = min(dstCost[components[i]], abs(i - componentToVertices[components[n - 1]][dstIdx]))

    minCost = min(srcCost[i]*srcCost[i] + dstCost[i]*dstCost[i] for i in range(n))
    print(minCost)

def main():
    t = int(input().strip())
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()
</pre>



[[Category:Yearly_2021_2022]]
[[Category:Silver]]
[[Category:Union-Find]]
[[Category:Graph]]
[[Category:Kruskal's Algorithm]]