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.
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)
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;
}
0 Comments