Cerinta completa

Let be a connected, directed graph with vertices numbered from to such that any vertex is reachable from vertex . In addition, any two distinct vertices, and , are connected by at most one edge .

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

  1. tree edge: If was discovered for the first time when we traversed .
  2. back edge: If was already on the stack when we tried to traverse .
  3. forward edge: If was already discovered while was on the stack.
  4. cross edge: Any edge that is not a tree, back, or forward edge.

To better understand this, consider the following C++ pseudocode:

// initially false
bool discovered[n]; 

// initially false
bool finished[n];   

vector<int> g[n];

void dfs(int u) {
    // u is on the stack now
    discovered[u] = true;
    for (int v: g[u]) {
        if (finished[v]) {
            // forward edge if u was on the stack when v was discovered
            // cross edge otherwise
            continue;
        }
        if (discovered[v]) {
            // back edge
            continue;
        }
        // tree edge
        dfs(v);
    }
    finished[u] = true;
    // u is no longer on the stack
}

Given four integers, , , , and , construct any graph having exactly tree edges, exactly back edges, exactly forward edges, and exactly cross edges. Then print according to the Output Format specified below.

Input Format

A single line of four space-separated integers describing the respective values of , , , and .

Constraints

Output Format

If there is no such graph , print -1; otherwise print the following:

  1. The first line must contain an integer, , denoting the number of vertices in .
  2. Each line of the subsequent lines must contain the following space-separated integers:
    • The first integer is the outdegree, , of vertex .
    • This is followed by distinct numbers, , denoting edges from to for . The order of each should be the order in which a DFS considers edges.

Sample Input 0

3 1 1 1

Sample Output 0

4
3 2 4 3
1 3
1 1
1 2

Explanation 0

The DFS traversal order is: . Thus, , and are tree edges; is a back edge; is a forward edge; and is a cross edge. This is demonstrated by the diagram below, in which tree edges are black, forward edges are blue, back edges are red, and cross edges are green.

Illustration to the first sample

Sample Input 1

1 10 20 30

Sample Output 1

-1

Explanation 1

No such graph exists satisfying the given values.

Limbajul de programare folosit: python3

Cod:

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)

Scor obtinut: 1.0

Submission ID: 464665640

Link challenge: https://www.hackerrank.com/challenges/dfs-edges/problem

DFS Edges