Soluție HackerRank pentru Black and White Tree. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: Black and White Tree

Cerinta completa

Nikita is making a graph as a birthday gift for her boyfriend, a fellow programmer! She drew an undirected connected graph with [Expresie matematică indisponibilă în copia arhivată] nodes numbered from [Expresie matematică indisponibilă în copia arhivată] to [Expresie matematică indisponibilă în copia arhivată] in her notebook.

Each node is shaded in either white or black. We define [Expresie matematică indisponibilă în copia arhivată] to be the number of white nodes, and [Expresie matematică indisponibilă în copia arhivată] to be the number of black nodes. The graph is drawn in such a way that:

  • No [Expresie matematică indisponibilă în copia arhivată] adjacent nodes have same coloring.
  • The value of [Expresie matematică indisponibilă în copia arhivată], which we’ll call [Expresie matematică indisponibilă în copia arhivată], is minimal.

Nikita’s mischievous little brother erased some of the edges and all of the coloring from her graph! As a result, the graph is now decomposed into one or more components. Because you’re her best friend, you’ve decided to help her reconstruct the graph by adding [Expresie matematică indisponibilă în copia arhivată] edges such that the aforementioned graph properties hold true.

Given the decomposed graph, construct and shade a valid connected graph such that the difference [Expresie matematică indisponibilă în copia arhivată] between its shaded nodes is minimal.

Input Format

The first line contains [Expresie matematică indisponibilă în copia arhivată] space-separated integers, [Expresie matematică indisponibilă în copia arhivată] (the number of nodes in the original graph) and [Expresie matematică indisponibilă în copia arhivată] (the number of edges in the decomposed graph), respectively.
The [Expresie matematică indisponibilă în copia arhivată] subsequent lines each contain [Expresie matematică indisponibilă în copia arhivată] space-separated integers, [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată], describing a bidirectional edge between nodes [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată] in the decomposed graph.

Constraints

  • [Expresie matematică indisponibilă în copia arhivată]
  • [Expresie matematică indisponibilă în copia arhivată]
  • It is guaranteed that every edge will be between [Expresie matematică indisponibilă în copia arhivată] distinct nodes, and there will never be more than [Expresie matematică indisponibilă în copia arhivată] edge between any [Expresie matematică indisponibilă în copia arhivată] nodes.
  • Your answer must meet the following criteria:
    • The graph is connected and no [Expresie matematică indisponibilă în copia arhivată] adjacent nodes have the same coloring.
    • The value of [Expresie matematică indisponibilă în copia arhivată] is minimal.
    • [Expresie matematică indisponibilă în copia arhivată]

Output Format

You must have [Expresie matematică indisponibilă în copia arhivată] lines of output.
The first line contains [Expresie matematică indisponibilă în copia arhivată] space-separated integers: [Expresie matematică indisponibilă în copia arhivată] (the minimum possible value of [Expresie matematică indisponibilă în copia arhivată]) and [Expresie matematică indisponibilă în copia arhivată] (the number of edges you’ve added to the graph), respectively.
Each of the [Expresie matematică indisponibilă în copia arhivată] subsequent lines contains [Expresie matematică indisponibilă în copia arhivată] space-separated integers, [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată], describing a newly-added bidirectional edge in your final graph (i.e.: new edge [Expresie matematică indisponibilă în copia arhivată]).

You may print any [Expresie matematică indisponibilă în copia arhivată] of the possible reconstructions of Nikita’s graph such that the value of [Expresie matematică indisponibilă în copia arhivată] in the reconstructed shaded graph is minimal.

Sample Input 0

 8 8
 1 2
 2 3
 3 4
 4 1
 1 5
 2 6
 3 7
 4 8

Sample output 0

0 0

Sample Input 1

 8 6
 1 2
 3 4
 3 5
 3 6
 3 7
 3 8

Sample Output 1

4 1
1 5

Sample Input 2

 5 4
 1 2
 2 3
 3 4
 4 1

Sample Output 2

  1 2
  2 5
  4 5

Explanation

In the figure below, the solid lines show the decomposed graph after Nikita’s brother erased the edges, and the dotted lines show one possible correct answer:

Trei exemple de arbori alb-negru; muchiile continue rămân, iar cele punctate arată muchii care pot fi adăugate.

In Sample [Expresie matematică indisponibilă în copia arhivată], no additional edges are added and [Expresie matematică indisponibilă în copia arhivată]. Because [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată], we get [Expresie matematică indisponibilă în copia arhivată]. Thus, we print [Expresie matematică indisponibilă în copia arhivată] on a new line (there is only [Expresie matematică indisponibilă în copia arhivată] line of output, as [Expresie matematică indisponibilă în copia arhivată]).

In Sample [Expresie matematică indisponibilă în copia arhivată], the only edge added is [Expresie matematică indisponibilă în copia arhivată], so [Expresie matematică indisponibilă în copia arhivată]. Here, [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată], so [Expresie matematică indisponibilă în copia arhivată]. Thus, we print [Expresie matematică indisponibilă în copia arhivată] on the first line. Next, we must print [Expresie matematică indisponibilă în copia arhivată] lines describing each edge added; because [Expresie matematică indisponibilă în copia arhivată], we print a single line describing the [Expresie matematică indisponibilă în copia arhivată] space-separated nodes connected by our new edge: [Expresie matematică indisponibilă în copia arhivată].

In Sample [Expresie matematică indisponibilă în copia arhivată], we can either add [Expresie matematică indisponibilă în copia arhivată] edge [Expresie matematică indisponibilă în copia arhivată] or [Expresie matematică indisponibilă în copia arhivată], or both of them. In both cases we get [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată], so [Expresie matematică indisponibilă în copia arhivată]. Thus [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată] or [Expresie matematică indisponibilă în copia arhivată] both are correct.

Limbajul de programare folosit: cpp14

Cod:

#include <bits/stdc++.h>
// #include "testlib.h"
using namespace std ;

#define ft first
#define sd second
#define pb push_back
#define all(x) x.begin(),x.end()

#define ll long long int
#define vi vector<int>
#define vii vector<pair<int,int> >
#define pii pair<int,int>
#define vl vector<ll>
#define vll vector<pair<ll,ll> >
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define mp make_pair

#define sc1(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d%d",&x,&y)
#define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define scll1(x) scanf("%lld",&x)
#define scll2(x,y) scanf("%lld%lld",&x,&y)
#define scll3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)

#define pr1(x) printf("%d\n",x)
#define pr2(x,y) printf("%d %d\n",x,y)
#define pr3(x,y,z) printf("%d %d %d\n",x,y,z)

#define prll1(x) printf("%lld\n",x)
#define prll2(x,y) printf("%lld %lld\n",x,y)
#define prll3(x,y,z) printf("%lld %lld %lld\n",x,y,z)

#define pr_vec(v) for(int i=0;i<v.size();i++) cout << v[i] << " " ;

#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)

#define fr(i, a, b) for(i=a; i<=b; i++)
#define fb(i, a, b) for(i=a; i>=b; i--)

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const int N=200010;
int w[2];
vector <int> v[N];
int a[N], d[N], p[N], c[N], col[N], sz, ccol[2][N];
bool f[N];
queue<int> q[N];
void dfs(int x,int y){
    f[x]=1;
    w[y]++;
    col[x] = y;
    ccol[y][sz] = x;
    for (int i=0;i<v[x].size();i++)
    if (!f[v[x][i]])
        dfs(v[x][i],(y^1));
    else if( col[v[x][i]] != 1 - y ) 
        assert(0);
}

int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=0,x,y;i<m;i++){
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }

    int k=0;
    for (int i=1;i<=n;i++) {
        if (!f[i]) {
            w[0] = w[1]=0;
            dfs(i,0);
            c[i] = (w[0] < w[1]);
            k+=abs(w[0]-w[1]);
            a[abs(w[0]-w[1])]++;
            q[abs(w[0]-w[1])].push( i );
        }
    }

    for (int j=1;j<=k;j++) d[j]=N;

    for (int i=1;i<=n;i++)
        if (a[i]) {
            for (int j=0;j+i<=k;j++) {
                if( d[i+j] == N && d[j] != N ) {
                    d[i+j] = d[j] + 1;
                    p[i+j] = j;
                }
            }

            for (int j=1;j<=k;j++) {
                if (d[j]>a[i]) {
                    d[j]=N;
                    p[j]=0;
                } else {
                    d[j]=0;
                }
            }
        }

    int ans=k, v = 0;
    for (int i=0;i<=k;i++) {
        if(d[i]<N) {
            if( ans >= abs(k - 2 * i) ) {
                ans = abs(k - 2 * i);
                v = i;
            }
        }
    }

    memset(f, 0, sizeof f);
    while( v != 0 ) {
        int diff = v - p[v];
        int nd = q[diff].front();
        q[diff].pop();
        sz ++;
        dfs(nd, c[nd]);
        v = p[v];
    }

    for(int i=1; i<=n; i++) {
        if( !f[i] ) {
            sz ++;
            dfs(i, 1 - c[i]);
        }
    }

    int blk, wht, idb, idw;
    blk = wht = idb = idw = -1;
    for(int i=1; i<=sz; i++) {

        if( ccol[0][i] ) {
            blk = ccol[0][i];
            idb = i;
        }

        if( ccol[1][i] ) {
            wht = ccol[1][i];
            idw = i;
        }
    }
    cout << ans << " " << sz - 1 << "\n";
    if( idb != idw ) cout << blk << " " << wht << "\n";
    for(int i=1; i<=sz; i++) {
        if( i != idb && i != idw ) {
            if( ccol[0][i] ) {
                cout << wht << " " << ccol[0][i] << "\n";
            } else {
                cout << blk << " " << ccol[1][i] << "\n";
            }
        }
    }
    return 0;
}

Scor obtinut: 1.0

Submission ID: 464650250

Link challenge: https://www.hackerrank.com/challenges/black-n-white-tree-1/problem

Black and White Tree