Road Construction

There are n cities and initially no roads between them. However, every day a new road will be constructed, and there will be a total of m$m$ roads.

A component is a group of cities where there is a route between any two cities using the roads. After each day, your task is to find the number of components and the size of the largest component.

Example:

Input: n = 5, m = 3, edges = {{1, 2}, {1, 3}, {4, 5}}

Output:

4 2
3 3
2 3

Approach:

C++

#include <bits/stdc++.h>
using namespace std;
int parent[1000001];
int size1[1000001];
void makeSet(int n)
{
    for (int i = 1; i <= n; i++)
    {
        parent[i] = i;
        size1[i] = 1;
    }
}
int find(int a)
{
    if (a == parent[a])
        return a;
    return parent[a] = find(parent[a]);
}
void unionSet(int a, int b)
{
    a = find(a);
    b = find(b);
    if (a != b)
    {
        if (size1[a] < size1[b])
            swap(a, b);
        parent[b] = a;
        size1[a] += size1[b];
    }
}
int main()
{
    int n = 5, m = 3;
    vector<vector<int>> edges = {{1, 2}, {1, 3}, {4, 5}};
    makeSet(n);
    int ans = INT_MIN, cc_count = n;
    for (int i = 0; i < m; i++)
    {
        int a = edges[i][0], b = edges[i][1];

        a = find(a);
        b = find(b);
        if (a != b)
            cc_count -= 1;
        unionSet(a, b);
        ans = max(ans, size1[a]);
        ans = max(ans, size1[b]);

        cout << cc_count << " " << ans << "\n";
    }
    return 0;
}