HackerRank DFS Edges problem solution

In this HackerRank DFS Edges problem solution we have given four integers, t, b, f, and c, construct any graph G having exactly t tree edges, exactly b back edges, exactly f forward edges, and exactly c cross edges. Then print G according to the Output Format specified.

Let G be a connected, directed graph with vertices numbered from l to n such that any vertex is reachable from vertex 1. In addition, any two distinct vertices, u and v, are connected by at most one edge (u,v).

Consider the standard DFS (Depth-First Search) algorithm starting from vertex 1. As every vertex is reachable, each edge (u,v) of G is classified by the algorithm into one of four groups:

• tree edge: If v was discovered for the first time when we traversed (u,v).
• back edge: If v was already on the stack when we tried to traverse (u,v).
• forward edge: If v was already discovered while u was on the stack.
• cross edge: Any edge that is not a tree, back, or forward edge.

HackerRank DFS Edges problem solution in Python.

import math
import os
import random
import re
import sys
def DepthFristSearch(argument):
    global finished
    global timer
    global t
    global b
    global f
    global c 
    global stack
    global discovery_times
    global depth
    global list_neibors
    #increment the time by one
    timer+= 1
    discovery_times[argument] = timer
    stack.append(argument)

    for goal in list_neibors[argument]:
        depth[goal] = depth[argument] + 1
        DepthFristSearch(goal)

    stack.pop()

    for vertex in stack:
        if b <= 0:
            break
        list_neibors[argument].append(vertex)
        b-=1


    for vertex in finished:
        if c <= 0 or discovery_times[vertex] >= discovery_times[argument]:
            break
        
        goal = vertex
        list_neibors[argument].append(goal)
        c-=1

    for vertex in finished:
        if f <= 0 or discovery_times[vertex] <= discovery_times[argument]:
            break
        goal = vertex
        if depth[goal] == depth[argument] + 1:
            continue
        list_neibors[argument].append(goal)
        f-=1

    finished.add(argument)



if __name__ == '__main__':
    tbfc = input().split()

    t = int(tbfc[0])

    b = int(tbfc[1])

    f = int(tbfc[2])

    c = int(tbfc[3])

    # Write Your Code Here
    n_vertices = t + 1 ## so we have number of vertices

    list_neibors = { i:list() for i in range(n_vertices) }
    stack = list()
    discovery_times = [0]*n_vertices
    depth = [0]*n_vertices
    timer = 0
    finished = set()
    minimum_height = max(f+t,b)
    maximum_height = ( n_vertices * (n_vertices-1) ) / 2 - c
    #check the canfind a graph or not
    if maximum_height < minimum_height: 
        print(-1)
        sys.exit()

    ## height of graph is numnber of tree edges

    sum_height = t 
    for i in range(1,n_vertices):
        if sum_height + i - 1 <= minimum_height:
            list_neibors[i-1].append(i)
            sum_height = sum_height + ( i - 1)
        else:
            list_neibors[minimum_height - sum_height].append(i)
            sum_height = sum_height + (minimum_height - sum_height)

    if sum_height < minimum_height:
        print(-1)
        sys.exit()
    DepthFristSearch(0)
    print(n_vertices)
    for i in list_neibors:
        print(len(list_neibors[i]))
        for v in list_neibors[i]:
            print(v+1)

DFS Edges problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {

  static List<Integer>[] g;

  static boolean left(int nodes, int f, int b) {
    for (int i = 1; i < nodes; i++) {
      g[i].add(i + 1);
    }
    int f0 = f;
    int b0 = b;
    int start = 1;
    while (f0 > 0 || b0 > 0) {
      int next = start + 1;
      if (next > nodes) {
        return false;
      }
      if (b0 > 0) {
        g[next].add(start);
        b0--;
      }      
      next++;
      while ((f0 > 0 || b0 > 0) && next <= nodes) {
        if (f0 > 0) {
          g[start].add(next);
          f0--;
        }
        if (b0 > 0) {
          g[next].add(start);
          b0--;
        }
        next++;
      }
      start++;
    }
    return true;
  }

  static boolean right(int start, int nodes, int c) {
    for (int i = start; i <= nodes; i++) {
      g[1].add(i);
    }
    int c0 = c;
    for (int i = nodes; i >= start; i--) {
      for (int j = i - 1; j > 1; j--) {
        g[i].add(j);
        c0--;
        if (c0 == 0) {
          break;
        }
      }
      if (c0 == 0) {
        break;
      }
    }
    if (c0 > 0) {
      return false;
    }
    return true;
  }

  static boolean complexn(int nodes, int t, int b, int f, int c) {
    int n = 1;
    int egges = nodes - n - 1;
    int last = nodes - n - 1;
    while (egges < c) {
      n++;
      last = egges;
      egges += nodes - n - 1;
    }
    n--;
    int left = nodes - n;
    for (int i = 1; i < left - 1; i++) {
      g[i].add(i + 1);
    }
    int crossNode = left - (c - last) - 1;
    g[crossNode].add(left);
    n = left - 1;
    int f0 = f;
    int b0 = b;
    int start = 1;
    while (f0 > 0 || b0 > 0) {
      int next = start + 1;
      if (next > n) {
        break;
      }
      if (b0 > 0) {
        g[next].add(start);
        b0--;
      }
      next++;
      while ((f0 > 0 || b0 > 0) && next <= n) {
        if (f0 > 0) {
          g[start].add(next);
          f0--;
        }
        if (b0 > 0) {
          g[next].add(start);
          b0--;
        }
        next++;
      }
      start++;
    }

    if (b0 > 0) {
      for (int i = 1; b0 > 0 && i <= crossNode; i++) {
        g[left].add(i);
        b0--;
      }
    }
    for (int i = 0; i < (c - last); i++) {
      g[left].add(crossNode + i + 1);
    }
    for (int i = 1; i < left && f0 > 0; i++) {
      g[i].add(left);
      f0--;
    }
    if (!right(left + 1, nodes, last)) {
      return false;
    }
    if (b0 > 0) {
      for (int i = left+1; b0 > 0 && i <= nodes; i++) {
        g[i].add(1);
        b0--;
      }
    }

    return true;
  }  

  static boolean complex1(int nodes, int t, int b, int f, int c) {
    int n = nodes - 1;
    for (int i = 1; i < n; i++) {
      g[i].add(i + 1);
    }
    int crossNode = nodes - c-1;
    g[crossNode].add(nodes);
    int f0 = f;
    int b0 = b;
    int start = 1;
    while (f0 > 0 || b0 > 0) {
      int next = start + 1;
      if (next > n) {
        break;
      }
      if (b0 > 0) {
        g[next].add(start);
        b0--;
      }
      next++;
      while ((f0 > 0 || b0 > 0) && next <= n) {
        if (f0 > 0) {
          g[start].add(next);
          f0--;
        }
        if (b0 > 0) {
          g[next].add(start);
          b0--;
        }
        next++;
      }
      start++;
    }

    for (int i = 1; i <= b0; i++) {
      g[nodes].add(i);
    }
    for (int i = 0; i < c; i++) {
      g[nodes].add(crossNode+i+1);
    }
    for (int i = 1; i <= f0; i++) {
      g[i].add(nodes);
    }

    return true;
  }
  
  @SuppressWarnings("unchecked")
  static boolean solve(int t, int b, int f, int c) {
    int nodes = t + 1;
    int maxEdges = nodes * (nodes - 1);
    if (t + b + f + c > maxEdges
        || f > maxEdges/2 
        || b + c > maxEdges/2) {
      return false;
    }
    g = new List[nodes + 1];
    for (int i = 1; i < g.length; i++) {
      g[i] = new ArrayList<>();
    }
    if (b + f + c == 0) {
      for (int i = 1; i < nodes; i++) {
        g[i].add(i + 1);
      }
      return true;
    }
    if (c == 0) {
      if (!left(nodes, f, b)) {
        return false;
      }
      return true;
    }
    if (b + f == 0) {
      if (!right(2, nodes, c)) {
        return false;
      }
      return true;
    }

    int n = 1;
    int egges = nodes - n-1;
    while (egges < c) {
      n++;
      egges += nodes - n-1;
    }
    int left = nodes - n;
    int tot = ((left - 1) * (left - 2)) / 2;
    if (b <= tot && f <= tot) {
      if (!left(left, f, b)) {
        return false;
      }
  
      if (!right(left + 1, nodes, c)) {
        return false;
      }
      return true;
    }
    
    if (n == 1 && complex1(nodes, t, b, f, c)) {
      return true;
    }

    if (left <= 2 && f == 0 && b < nodes) {
      if (!right(2, nodes, c)) {
        return false;
      }
      for (int i = 2; i <= b+1; i++) {
        g[i].add(1);
      }
      return true;
    }

    if (complexn(nodes, t, b, f, c)) {
      return true;
    }

    return false;
  }

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());

    int t = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());
    int f = Integer.parseInt(st.nextToken());
    int c = Integer.parseInt(st.nextToken());

    if (solve(t, b, f, c)) {
      bw.write((g.length - 1) + "n");
      for (int i = 1; i < g.length; i++) {
        bw.write(String.valueOf(g[i].size()));
        for (int x : g[i]) {
          bw.write(" " + x);
        }
        bw.write("n");
      }
    } else {
      bw.write("-1");
    }

    bw.newLine();

    bw.close();
    br.close();
  }

}

Problem solution in C++.

#include <bits/stdc++.h>

using namespace std;

#define sz(x) ((int) (x).size())
#define forn(i,n) for (int i = 0; i < int(n); ++i)
#define forab(i,a,b) for (int i = int(a); i < int(b); ++i)

#define forward forward1

const int maxn = 2e5;

vector<int> g[maxn];
int tree, back, forward, cross;

int in[maxn], h[maxn];
int timer;

set<pair<int, int>> finished;
vector<int> st;

void dfs(int u)
{
    in[u] = timer++;
    st.push_back(u);

    for (int v: g[u])
    {
        h[v] = h[u] + 1;
        dfs(v);
    }

    st.pop_back();

    for (int v: st)
    {
        if (back <= 0)
            break;
        g[u].push_back(v);
        --back;
    }
    for (auto p: finished)
    {
        if (cross <= 0)
            break;
        if (p.first >= in[u])
            break;
        int v = p.second;
        g[u].push_back(v);
        --cross;
    }
    for (auto it = finished.rbegin(); it != finished.rend(); ++it)
    {
        if (forward <= 0)
            break;
        if (it->first <= in[u])
            break;
        int v = it->second;
        if (h[v] == h[u] + 1)
            continue;
        g[u].push_back(v);
        --forward;
    }

    finished.emplace(in[u], u);
}

int main()
{
    cin >> tree >> back >> forward >> cross;
    int n = tree + 1;
    int minSumH = max(tree + forward, back);
    int maxSumH = n * (n - 1) / 2 - cross;
    if (maxSumH < minSumH)
    {
        cout << -1 << 'n';
        return 0;
    }
    int sumH = tree;
    forab (i, 1, n)
    {
        if (sumH + i - 1 <= minSumH)
        {
            g[i - 1].push_back(i);
            sumH += i - 1;
        }
        else
        {
            g[minSumH - sumH].push_back(i);
            sumH += minSumH - sumH;
        }
    }
    if (sumH < minSumH)
    {
        cout << -1 << 'n';
        return 0;
    }
    dfs(0);
    assert(back == 0);
    assert(forward == 0);
    assert(cross == 0);
    assert(sumH == accumulate(h, h + n, 0));
    cout << n << 'n';
    forn (i, n)
    {
        cout << sz(g[i]);
        for (int v: g[i])
            cout << ' ' << v + 1;
        cout << 'n';
    }
    return 0;
}