Question

In this program you will read a file specifying a directed graph G as a list of edges. Each edge u →v is listed on one line as u v. The input file simply lists the edges in arbitrary order as pairs of vertices, with each edge on a separate line. The vertices are numbered in order from 1 to the total number of vertices. The program outputs the out-degree sequence for G^SCC in increasing order.

For example for the input below:

2 1

3 2

1 3

1 5

3 4

4 5

6 7

5 6

7 4

3 11

2 8

8 9

10 8

9 10

9 4

9 7

10 11

7 11

6 11

the corresponding output is:

0 1 2 3

You should be able to implement this program to run in linear time (time proportional to the total number of vertices plus the total number of edges in the input graph)

Answer 1

Solution:

• Since language of code is not mentioned, I will be using Python
• Store the input in file named "input.txt"

Code: Explaination

• Store out degree count for each vertex in a list
• Copy the out degree count to a set. This will ensure final result will have only distinct values and also set keep those values in increasing order.
• Print the result accordingly

file = open('input.txt', 'r')
input_lines = file.readlines()

# Assuming maximum number of vertices are 100
list_outdegree = [0]*100

# split each line of input u and v vertex
for line in input_lines:
    edge = line.split(' ')
    u = int(edge[0])
    v = int(edge[1])

    # Add one to out-degree count of u vertex
    list_outdegree[u] += 1
    
    
# Set stores distinct number of out-degrees count and store it in increasing order
set_degree = set()
for degree in list_outdegree:
    set_degree.add(degree)
    

# print output as required
for d in set_degree:
    print(d, end=' ')

Output:

0 1 2 3 

Screeshot is attached, to understand indentation used in the python code

PS: Let me know if you have any doubts.