Skip to content
Programmingoneonone
Programmingoneonone
  • Engineering Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
    • 100+ C++ Programs
  • Solutions
    • HackerRank
      • Algorithms Solutions
      • C solutions
      • C++ solutions
      • Java solutions
      • Python solutions
      • Data Structures Solutions
    • Leetcode Solutions
    • HackerEarth Solutions
  • Work with US
Programmingoneonone
Programmingoneonone

HackerRank DFS Edges problem solution

YASH PAL, 31 July 202425 January 2026

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

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

Algorithms coding problems solutions AlgorithmsHackerRank

Post navigation

Previous post
Next post

Programmingoneonone

We at Programmingoneonone, also known as Programming101 is a learning hub of programming and other related stuff. We provide free learning tutorials/articles related to programming and other technical stuff to people who are eager to learn about it.

Pages

  • About US
  • Contact US
  • Privacy Policy

Practice

  • Java
  • C++
  • C

Follow US

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