Skip to content
Programmingoneonone
Programmingoneonone

Learn everything about programming

  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
    • Cybersecurity
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone
Programmingoneonone

Learn everything about programming

HackerRank DFS Edges problem solution

YASH PAL, 31 July 202430 November 2025

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.

HackerRank DFS Edges problem solution

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)

{“mode”:”full”,”isActive”:false}

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();
  }

}

{“mode”:”full”,”isActive”:false}

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;
}

{“mode”:”full”,”isActive”:false}

Algorithms coding problems solutions AlgorithmsHackerRank

Post navigation

Previous post
Next post

Are you a student and stuck with your career or worried about real-time things, and don't know how to manage your learning phase? Which profession to choose? and how to learn new things according to your goal, and land a dream job. Then this might help to you.

Hi My name is YASH PAL, founder of this Blog and a Senior Software engineer with 5+ years of Industry experience. I personally helped 40+ students to make a clear goal in their professional lives. Just book a one-on-one personal call with me for 30 minutes for 300 Rupees. Ask all your doubts and questions related to your career to set a clear roadmap for your professional life.

Book session - https://wa.me/qr/JQ2LAS7AASE2M1

Pages

  • About US
  • Contact US
  • Privacy Policy

Follow US

  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2026 Programmingoneonone | WordPress Theme by SuperbThemes