Contents
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
bc chutiya samjha he kya , site pe likh rakha he ki solution denge aur madarchod fir solution na dekar poora question firse repeat ka rakha he , ja bsdk gaand mara madarchod.
Sorry for the inconvenience, their might be issue with the download link we have updated the solution directly. Please be respectful as we really try our best to provide solution.