Maximise the bridges MAXBRIDGE Solution Codechef

Maximise the bridges MAXBRIDGE Solution

Chef is given two integers N and M. Please help Chef find any connected undirected graph G consisting of exactly N vertices and M edges, such that the number of bridges in G is maximized (among all graphs with N vertices and M edges). G cannot have self-loops or multiple edges.

If there is more than one connected undirected graph with the maximum number of bridges, you may print any one of them.

Note: A bridge is an edge whose removal increases the number of connected components of the graph.

Input Format

• The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
• Each testcase consists of a single line of input, containing two integers N,M the number of vertices and edges of the graph you must construct.

Output Format

For each test case, output M lines where the i-th line contains two space-separated integers denoting the i-th edge of the graph G you constructed. The edges may be printed in any order, and for each edge the endpoints may be printed in any order.

Note that G must not contain self-loops or multiple edges, and no other graph on N vertices and M edges can contain strictly more bridges than G.

Constraints

• 1≤T≤103
• 2≤N≤103
• N−1≤M≤min(N⋅(N−1)/2,105)
• Sum of N over all test cases do not exceed 103
• Sum of M over all test cases do not exceed 105

Subtasks

• Subtask 1 (100 points): Original constraints

Sample Input 1

3
4 4
5 4
3 3

Sample Output 1

1 2
2 3
3 4
1 3
1 2
2 3
3 4
4 5
1 2
2 3
3 1

Explanation

Test case 1: There is exactly 1 bridge in the graph and it cannot be increased further.

• 

Test case 2: Since M=N−1 and we are required to output a connected graph, the graph will always be a tree and hence have 4 bridges. Any tree is acceptable here.

• 

Test case 3: Since M=N⋅(N−1)/2 our only choice is a complete graph, which has 0 bridges.

• 

SOLUTION

Program Python: Maximise the bridges MAXBRIDGE Solution in Python

# cook your dish here
for _ in range(int(input())):
    a,b=map(int,input().split())
    c={a:[]}
    for i in range(1,a):
        c[i]=[i+1]
        print(i,i+1)
        b-=1
    flg=3
    while b>0:
        for j in range(1,flg):
            
            if c[j][-1]<flg:
                c[j].append(flg)
                print(j,flg)
                b-=1
                if b==0:
                    break
        flg+=1

Program C++: Maximise the bridges MAXBRIDGE Solution in C++

#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
    int n,m;
    
    cin>>n>>m;
    
    map<int ,int> x;
    
    for(int i=1;i<n;i++){
    
        x[i]=i+1;
        
        cout<<i<<" "<<i+1<<"\n";
        
        m=m-1;
        
    }
    
    int last=3;
    
    while(m>0){
    
        for(int i=1;i<last;i++){
        
            if (x[i]<last){
            
                x.insert (std::pair<int,int>(i,last));
                
                cout<<i<<" "<<last<<"\n";
                
                m=m-1;
                
                if(m==0){
                
                    break;
                    
                }}}
                
        last=last+1;
        
    }}
	return 0;
}

Program Java: Maximise the bridges MAXBRIDGE Solution in Java

/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
    
    static Scanner sc = new Scanner(System.in);
	
	static void solutionWithArray() {
	    int n = sc.nextInt();
	    int a[] = new int[n];
	    for(int i = 0; i < n; i++) {
	        a[i] = sc.nextInt();
	    }
	}
	
	static void solutionWithoutArray() {
	    int n = sc.nextInt();
	    int m = sc.nextInt();
	    for (int  i = 1; i <= n - 1; i++) {
	        System.out.println(i + " " + (i + 1));
	    }
	    m -= (n - 1);
	    int max = 3;
	    while (m != 0) {
	        for (int i = 1; i <= max - 2; i++) {
	            if (m == 0) {
	                break;
	            }
	            System.out.println(i + " " + max);
	            m--;
	        }
	        max++;
	    }
	}
	
	public static void main (String[] args) throws java.lang.Exception
	{
		int t = sc.nextInt();
		while(t-->0)
		{
		    solutionWithoutArray();
		}
	}
    
}

November Long Challenge 2021 Solution

• Which Fuel is Cheaper CHEAPFUEL Solution
• Convex Hulk CONHULK Solution
• Functional Array FUNARR Solution
• Flip or Compress FLIPCOMP Solution
• Maximise the bridges MAXBRIDGE Solution
• Wildcard Replacement WLDRPL Solution
• Xor Equation XOREQN Solution
• Hill Sequence HILLSEQ Solution
• Weird Palindrome Making MAKEPAL Solution
• Equal Coins EQUALCOIN Solution Codechef