Maximise the bridges MAXBRIDGE Solution Codechef

Maximise the bridges MAXBRIDGE Solution

Chef is given two integers NN and MM. Please help Chef find any connected undirected graph GG consisting of exactly NN vertices and MM edges, such that the number of bridges in GG is maximized (among all graphs with NN vertices and MM edges). GG 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 TT, denoting the number of test cases. The description of TT test cases follows.
• Each testcase consists of a single line of input, containing two integers N,MN,M – the number of vertices and edges of the graph you must construct.

Output Format

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

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

Constraints

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

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 11: There is exactly 11 bridge in the graph and it cannot be increased further.

• 

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

• 

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

• 

Maximise the bridges MAXBRIDGE Solution is updated. Click Below

SOLUTION

Program Python: Maximise the bridges MAXBRIDGE Solution in Python

Note: Solution Credit to Innovative Idea

# 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

Codechef Long Challenges Solution

October Long Challenge 2021 Solution

• Longest AND Subarray
• MEX-OR
• Digit Removal
• Yet another MEX problem
• Characteristic Polynomial Verification
• Chef at the Olympics
• Which Mixture
• Three Boxes

September Long Challenge 2021 Solution

• Airline Restrictions
• Travel Pass
• Shuffling Parities
• XOR Equal
• 2-D Point Meeting
• Minimize Digit Sum
• Minimum Digit Sum 2
• Treasure Hunt
• Covaxin vs Covishield