MAXBRIDGE - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Srikkanth R and Utkarsh Gupta
Tester: Manan Grover
Editorialist: Taranpreet Singh

DIFFICULTY

Easy

PREREQUISITES

Constructive algorithms, Graph

PROBLEM

Given N and M, find a connected undirected simple graph with N nodes and M edges having the maximum number of bridges. If multiple such graphs exist, print any.

A bridge is an edge in a graph such that removing this edge increases the number of connected components in the graph.

EXPLANATION

I’m going to explain a bit of complicated construction. There exist far simpler constructions, but this one I believe would be more instructive. For a simpler solution, refer solutions section.

When M = N-1

We have N nodes and N-1 edges. The required graph is any tree, and each edge of the tree is a bridge. Hence, we get N-1 bridges.

When M = N*(N-1)/2

In this case, an edge exists between each pair of nodes in the given graph. The number of bridges is 0 for N \geq 3 and exactly one bridge for N = 2.

General case

Let’s assume X is the maximum number of bridges. Then there must be X+1 cyclic components in the graph, such that these X edges connect them.

Let’s assume sizes of these components are S_1, S_2 \ldots S_{X+1} where \displaystyle \sum_{i = 1}^{X+1} S_i = N holds.

What is the number of edges you can add to these components? It is \displaystyle \sum_{i = 1}^{X+1} S_i*(S_i-1)/2.

The above quantity is maximized, when we make X components of size one and last components of size N-X. The maximum number of edges we can add is (N-X)*(N-X-1)/2 + X (Added number of edges inside last component and the X bridges.)

So, if M \leq (N-X)*(N-X-1)/2 + X, then we can have at least X bridges. We can find the largest X such that this inequality holds.

Construction

There can be multiple constrictions for this problem. I’d share mine here.

Dividing N nodes into X+1 components, first X components consisting of 1 node each, and last component consisting of N-X nodes. First add edges from i to $N for 1 \leq i \leq X. Then keep adding edges in last component until graph contains M edges.

Note

Although this construction was not the easiest one, this one gives an idea of how mathematical proofs can be applied in graph problems naturally. There’s also a very simple construction (as compared to this), which I have attached below.

TIME COMPLEXITY

SOLUTIONS

Setter's Solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#include <chrono>
#include <random>
#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define loop(i,a,b) for(ll i=a;i<=b;i++)
#define vi vector <int>
#define vs vector <string>
#define vc vector <char>
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define deb(x) cerr<<#x<<' '<<'='<<' '<<x<<'\n'
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(val)  no. of elements strictly less than val
// s.find_by_order(i)  itertor to ith element (0 indexed)
typedef vector<vector<ll>> matrix;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
void solve()
{
    ll n,m;
    cin>>n>>m;
    for(ll i=1;i<=n;i++)
    {
        ll temp=(i*(i-1))/2;
        temp+=(n-i);
        if(temp>=m)
        {
            int cnt=0;
            for(int j=i+1;j<=n;j++)
            {
                cout<<1<<' '<<j<<'\n';
                cnt++;
                if(cnt==m)
                    break;
            }
            for(int j=1;j<=i;j++)
            {
                for(int k=j+1;k<=i;k++)
                {
                    if(cnt==m)
                        break;
                    cout<<j<<' '<<k<<'\n';
                    cnt++;
                }
            }
            break;
        }
    }
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T=1;
    cin>>T;
    int t=0;
    while(t++<T)
    {
        //cout<<"Case #"<<t<<":"<<' ';
        solve();
        //cout<<'\n';
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Tester's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define asc(i,a,n) for(I i=a;i<n;i++)
#define dsc(i,a,n) for(I i=n-1;i>=a;i--)
#define forw(it,x) for(A it=(x).begin();it!=(x).end();it++)
#define bacw(it,x) for(A it=(x).rbegin();it!=(x).rend();it++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lb(x) lower_bound(x)
#define ub(x) upper_bound(x)
#define fbo(x) find_by_order(x)
#define ook(x) order_of_key(x)
#define all(x) (x).begin(),(x).end()
#define sz(x) (I)((x).size())
#define clr(x) (x).clear()
#define U unsigned
#define I long long int
#define S string
#define C char
#define D long double
#define A auto
#define B bool
#define CM(x) complex<x>
#define V(x) vector<x>
#define P(x,y) pair<x,y>
#define OS(x) set<x>
#define US(x) unordered_set<x>
#define OMS(x) multiset<x>
#define UMS(x) unordered_multiset<x>
#define OM(x,y) map<x,y>
#define UM(x,y) unordered_map<x,y>
#define OMM(x,y) multimap<x,y>
#define UMM(x,y) unordered_multimap<x,y>
#define BS(x) bitset<x>
#define L(x) list<x>
#define Q(x) queue<x>
#define PBS(x) tree<x,null_type,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define PBM(x,y) tree<x,y,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define pi (D)acos(-1)
#define md 1000000007
#define rnd randGen(rng)
int main(){
  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  uniform_int_distribution<I> randGen;
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  #ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  #endif
  I t;
  cin>>t;
  while(t--){
    I n,m;
    cin>>n>>m;
    V(P(I,I)) ans;
    asc(i,0,n-1){
      ans.pb({i+1,i+2});
    }
    m-=n-1;
    asc(i,0,n){
      if(m==0){
        break;
      }
      dsc(j,0,i-1){
        if(m==0){
          break;
        }
        ans.pb({i+1,j+1});
        m--;
      }
    }
    asc(i,0,sz(ans)){
      cout<<ans[i].fi<<" "<<ans[i].se<<"\n";
    }
  }
  return 0;
}
Editorialist's Model Solution
import java.util.*;
import java.io.*;
class MAXBRIDGE{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni(), M = ni();
        int X = N-1;
        while(((N-X)*(long)(N-X-1))/2+X < M)X--;
        
        for(int i = 1; i<= X; i++){
            pn(i+" "+N);
            M--;
        }
        
        for(int i = X+1; i<= N; i++){
            for(int j = i+1; j<= N; j++){
                if(M > 0){
                    pn(i+" "+j);
                    M--;
                }
            }
        }
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new MAXBRIDGE().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}
Editorialist's Simple Solution
import java.util.*;
import java.io.*;
class MAXBRIDGE{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni(), M = ni();
        for(int i = 2; i<= N; i++)pn(1+" "+i);
        M -= N-1;
        for(int i = 3; i<= N; i++){
            for(int j = 2; j< i && M > 0; j++, M--){
                pn(j+" "+i);
            }
        }
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new MAXBRIDGE().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

Hi, is this the correct place to share my solution?

I am not sure why my code is failing the tests. Any help would be great! Here is my solution:
[Solution: 53847739 | CodeChef]

Because your solution is not optimal.
for eg.
1
6 8
Correct answer :-
1 2
2 3
3 4
4 5
5 6
1 3
1 4
2 4
Where my solution(for above example) has 2 bridges left, so when we break those bridges I can make 2 connected components, on the other hand your solution do not have bridges so you cannot make any.
And Question is maximize the bridges so that you can break and make connected components as much as possible.

https://www.codechef.com/viewsolution/53681063

This passes 3 test cases. Please tell error in this?

You are not checking m>0 inside the inner while loop, so it can print more than m values. Here’s the correct solution Solution: 53889834 | CodeChef

oh! Thank You :smiley:

Hi Rinnersharingan, thanks for the reply, however I don’t quite understand, because the output of my code for
1
6 8

is exactly what you put above as the correct answer. So where am I going wrong??

Sorry brother. Now pasted correct output. :sweat_smile: