CSES - Road Construction

Explanation

We can represent the problem as an undirected graph, with each of the $n$ cities being a node and each of the $m$ roads being an edge. We then have two subproblems we need to consider:

Our first subproblem is counting the number of connected components each day. We can count them using Disjoint Set Union (DSU), where each tree in the structure represents a connected component. We start off with $n$ cities and no roads between them, and thus $n$ connected components. For every road that is built, we unite the two cities the road connects. If the union is successful, then two different connected components have been joined into one, and thus the number of connected components decreases by 1.

Our second subproblem is finding the size of the largest connected component each day. Conveniently, the DSU optimization union-by-size stores the size of any node's component in that tree's parent node. Furthermore, the largest component will only change if a union is successful, as otherwise the graph stays the same. If a union happens, we check if the size of the tree which was added to during uniting is a new maximum.

Implementation

Time Complexity: $\mathcal{O}(M \cdot \alpha(N))$

Copy
#include <bits/stdc++.h>

using namespace std;

struct DSU {
	vector<int> e;
	void init(int n) { e = vector<int>(n, -1); }
	int get(int x) { return (e[x] < 0 ? x : e[x] = get(e[x])); }
	bool sameSet(int x, int y) { return get(x) == get(y); }
	int size(int x) { return -e[get(x)]; }

Copy
import sys

input = sys.stdin.readline  # speed up input to not TLE

 Code Snippet: Disjoint Set Union (Click to expand)

n, m = map(int, input().split())

cities = DisjointSetUnion(n)
largest_size = 1

Copy
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class cses1676 {
	public static int[] disjoint;