CODEWITHSUNDEEP
algorithmgraph
HackAround
HackAround

Reputation: 85

Construct any bipartite graph with degree constraints

We need to construct a bipartite graph with N vertices each, on the two parts, and with total number of edges equal to M.

Given four integers N, M, X, Y we need to construct some bipartite graph satisfying this property. If there does not exist any such graph, then also tell the same.

Example : If N=2 , M=3 , X=1 and Y=2 then the 3 edges in bipartite graph will be : (1,1),(2,2) and (1,2)

If N=2 , M=3 , X=1 and Y=1 then no bipartite graph exists.

How can this problem be solved if 

1 ≤ N ≤ 100
1 ≤ X ≤ Y ≤ N 
0 ≤ M ≤ N * N

Original question link

Upvotes: 1

Views: 507

Answers (2)

Shubham
Shubham

Reputation: 2855

ACM ICPC 2016 India Preliminary Round Problem.

Link

The contest is now ended. I couldn't submit the answer (was about to submit the code just 10 secs before the end and my Internet stopped working).

d is equivalent to X in the OP's version of the problem.

D is equivalent to Y in the OP's version of the problem.

t is the number of test cases.

I made the code as per the original question in the link.

The logic is similar to Nico Schertler's one. My complexity will be a little more because instead of just connecting, i+xth node to i in the xth iteration, I have used a set that finds the first element not connected in the range [1..N] and connects them.

This is my code:

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


int main() {

    int t, n, m, d, D;
    cin >> t;
    while(t--) {
        cin >> n >> m >> d >> D;
        if(n*D < m || n*d > m)
            printf("-1\n");
        else {
            vector <set <int> > v(n);
            int edges = 0, count = 0;
            while(count != d) {
                for(int i = 0; i < n; i++) {
                    for(int j = 0; j < n; j++) {
                        if(v[i].find(j) == v[i].end()) {
                            v[i].insert(j);
                            ++edges;
                            break;
                        }
                        if(edges == m)
                            break;
                    }
                    if(edges == m)
                        break;
                }   
                ++count;
            }

            while(edges < m) {
                for(int i = 0; i < n; i++) {
                    if(v[i].size() == D)
                        continue;
                    for(int j = 0; j < n; j++) {
                        if(v[i].find(j) == v[i].end()) {
                            v[i].insert(j);
                            ++edges;
                            break;
                        }
                        if(edges == m)
                            break;
                    }
                    if(edges == m)
                        break;
                }
            }
            for(int i = 0; i < n; i++) {
                set <int>::iterator it = v[i].begin();
                for(; it != v[i].end(); ++it) {
                    printf("%d %d\n", i+1, (*it)+1);
                }
            }
        }
    }
    return 0;
}

I don't know whether this code is correct or not.

Upvotes: 0

Nico Schertler
Nico Schertler

Reputation: 32627

Obviously, the variables need to satisfy:

X * N <= M <= Y * N

Otherwise, there will be no solution.

Finding the edges could be done in waves. Start by connecting each node i from the first set to the according node i from the second set. In the next wave, connect i with (i + 1) mod N. Then i with (i + 2) mod N and so one. This will increase the degree of each vertex by exactly one in each wave. Stop whenever you have constructed M edges. This may also happen during a wave.

Upvotes: 1

Related Questions