BEUTYCON - Editorial

PROBLEM LINK:

Beautiful Country

Author: Champion_patel
Tester: Champion_patel , Chef_oggy , chef_hamster
Editorialist: Champion_patel

DIFFICULTY:

Medium

PROBLEM:

You are given a undirected graph and you have to print number of edges we have to add to satisfy condition that if there is path between x and z then there should be path between all y and z where x < y < z,

Prerequisites:

knowledge of DFS algorithm or DSU.

QUICK EXPLANATION:

we have to run DFS on every component from starting vertex and find max vertex in that component and if min vertex of next component is lesser than current max then we will increment answer by 1. we can also solve this question using DSU.

EXPLANATION:

First of all we will take input and store it in adjacency list.

In this approach we will iterate over all component and if we encounter any overlapping component which is not connected then we will add edge between those two component.

To implement this idea we will keep visited array for DFS and apply DFS on every vertex starting from 0. We will also store max element of component while applying DFS and if we encounter a vertex which is not visited and which is lesser than max vertex of previous component then we will increment our answer by 1.

SOLUTIONS:

Setter’s Solution

#define N  200005

vector<ll>v[N];
bool vis[N];
ll mx=-inf;

void dfs(ll n)
{
    vis[n]=1;
    mx=max(mx, n);

    for(auto it : v[n])if(!vis[it] )dfs(it);
}

int main()
{

    ll t;
    ll m,n,b,c,d,i,j,k,z,l,q,r;

    ll cnt=0,ans=0,sum=0;
    cin>>n>>m;
   for(int i=0;i<m;i++)
    {
        ll x,y;
        cin>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }
    mem(vis, 0);


    for(int i=0;i<n;i++)
    {
        if(!vis[i])
        {
            if( i<mx)ans++;
            dfs(i);
        }
    }
    cout<<ans<<endl;


return 0;
}

Tester’s Solution


#include <bits/stdc++.h> 

#define loop(i,m,n) for(ll i=m;i<n;i++)
#define rev(i,m,n) for(ll i=m;i>=n;i--)
#define ll long long
#define in(n) cin>>n
#define out(n) cout<<n<<"\n"
#define o(n) cout<<n<<" "
#define nl cout<<"\n"
#define yes cout<<"YES"<<"\n"
#define no cout<<"NO"<<"\n"
#define pb push_back
#define ppb pop_back
#define size(x) x.size()
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define MAX(x) *max_element(all(x))
#define MIN(x) *min_element(all(x))
#define SUM(x) accumulate(all(x), 0LL)
#define SORT(x) is_sorted(all(x))
#define lcm(x,y) (x*y)/__gcd(x,y)
#define dgt(n) floor(log10(n)+1)
#define point cout<<fixed<<setprecision(10)
#define debug(x) cout<<#x<<" "<<x<<"\n";
#define print(v) for(auto x : v)  o(x);  nl; 
#define ub(v,val) upper_bound(all(v),val)-v.begin()
#define lb(v,val) lower_bound(all(v),val)-v.begin()
const long long M = 1e9 + 7;
const long long inf = LONG_LONG_MAX;

using namespace std; 

//--------------------[...Never Used Functions...]---------------------//
ll binpow(ll a, ll b){   ll res=1;      while(b>0){     if(b&1) res=res*a;    a=a*a; b>>=1;    }       return res;     }
ll powmod(ll a, ll b, ll m) {ll ans = 1; while (b) {if (b & 1) {ans = (ans * a) % m;} a = (a * a) % m; b = b >> 1;} return ans % m;}
vector<ll> div(ll n){   vector<ll> v;   for(int i=1; i<=sqrt(n); i++){     if (n%i == 0){   v.pb(i);    if(n/i!=i) v.pb(n/i);  }   }   return v;   }
vector<ll> primediv(ll n){  vector<ll> v;   for(ll i=2;i<=sqrt(n);i++){   while(n%i==0){ n=n/i; v.pb(i); }  }   if(n>1) v.pb(n);    return v;   }
ll modINV(ll n,ll mod){      return powmod(n,mod-2,mod);    }
ll ncrmod(ll n,ll r,ll p){  if(r==0)     return 1;   unsigned long long fac[n + 1]={1};  for(int i=1;i<=n;i++)    fac[i]=(fac[i-1]*i)%p;  return (((fac[n]*modINV(fac[r],p))%p)*modINV(fac[n-r],p))%p;  }
double logg(ll n,ll k){   return log2(n)/log2(k);   }
//---------------------------------------------------------------------//

//------------------------[...DSU...]------------------------//
ll parent[200007];   ll Size[200007];
void make(ll v){   parent[v]=v;    Size[v]=1;  }
ll find(ll v){    if(v==parent[v])    return v;       return parent[v] = find(parent[v]);     }
void Union(ll a,ll b){   a = find(a);    b = find(b);    if(a!=b){   if(Size[a] < Size[b])   swap(a,b);      parent[b] = a;      Size[a] += Size[b];     }      }
//----------------------------------------------------------//

void drizzle()
{
    ll n,k;     in(n>>k);

    loop(i,0,n)       make(i);

    loop(i,0,k)
    {
        ll x,y;     in(x>>y);
        Union(x,y);
    }

    ll cnt=0;
    for(ll l=0;l<n;)
    {
        ll x = Size[find(l)];
        loop(j,l,l+x)
        {
            if(find(l)==find(j))        continue;
            Union(l,j);
            cnt++;
            x=Size[find(l)];
        }
        l+=x;
    }
    out(cnt);

    return;
}

int main()
{
    ios_base::sync_with_stdio(false);       
    cin.tie(nullptr);         
    cout.tie(nullptr);
    
    int testcase=1;     
    // cin>>testcase;

    while(testcase--)
    {
        drizzle();
    }

    return 0;
}

Tester’s solution

import java.util.*;

public class Main {

    static int n, m, u, v, ans = 0, mx = -1;
    static ArrayList<ArrayList<Integer>> edge = new ArrayList<>();
    static ArrayList<Integer> vis = new ArrayList<>();

    static void solve(int x) {
        vis.set(x, 1);
        mx = Math.max(x, mx);
        for (int i = 0; i < edge.get(x).size(); i++) {
            int next = edge.get(x).get(i);
            if (vis.get(next) == 0) {
                solve(next);
            }
        }
    }

    static void Champion_Patel() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        edge = new ArrayList<>();
        vis = new ArrayList<>();
        for (int i = 0; i < n + 1; i++) {
            edge.add(new ArrayList<>());
            vis.add(0);
        }
        for (int i = 1; i <= m; i++) {
            u = sc.nextInt();
            v = sc.nextInt();
            edge.get(u).add(v);
            edge.get(v).add(u);
        }
        int i = 0;
        while (i < n) {
            while (vis.get(i) == 1) {
                i++;
            }
            if (i < mx) {
                ans++;
            }
            solve(i);
        }
        System.out.println(ans);
    }

    public static void main(String[] args) {
        Champion_Patel();
    }
}