Competitive Programming Solutions

330B - Road Construction

26 Dec 2020 — Tags: graph,brute_force — URL

Note that the constraint (distance between pairs is at most $2$) will only be satisfied by a star graph (all nodes connected to a center node). The problem reduces to find a center for such graph and connect all other nodes to it.

Note that there’s always an answer because of the $m < \frac{n}{2}$ constraint.

Time complexity: $O(n)$

Memory complexity: $O(n)$

Click to show code.

 

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector<bool> is_center(n, true);
    while (m--)
    {
        int u, v;
        cin >> u >> v, u--, v--;
        is_center[u] = is_center[v] = false;
    }
    int root =
        distance(begin(is_center),
                 find_if(begin(is_center), end(is_center), [](bool flag) { return flag; }));
    cout << n - 1 << endl;
    for (int u = 0; u < n; ++u)
    {
        if (u == root)
            continue;
        cout << root + 1 << " " << u + 1 << endl;
    }
    return 0;
}

Related posts