Competitive Programming Solutions

402C - Searching For Graph

29 Dec 2020 — Tags: greedy,graphs,constructive — URL

So, intuitively, we want edges to be uniformly distributed on the vertices, as to minimize the maximum edges for each subgraph in the hope that it fits the problem’s constraints.

One way to do so is to add edges in lexicographical order.

Time complexity: $O(n)$

Memory complexity: $O(1)$

Click to show code.

 

using namespace std;
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n, p, m;
        cin >> n >> p;
        m = 2 * n + p;
        for (int u = 1; u < n; ++u)
        {
            for (int v = u + 1; v <= n; ++v)
            {
                if (!m)
                    break;
                cout << u << " " << v << endl;
                m--;
            }
            if (!m)
                break;
        }
    }
    return 0;
}

Related posts