[CSED233-01] 2025 Spring, Data Structure, POSTECH PA #4
Programming Assignment #4
Lecturer: Prof. Seung-Hwan Baek
Teaching Assistants: Suhyun Shin, Jinnyeong Kim, Hungyu Jeong, Eunsue Choi
**** PLEASE READ THIS GRAY BOX CAREFULLY BEFORE STARTING THE ASSIGNMENT ****
Due date: 11:59 PM May 28, 2025
Evaluation policy:
● Late submission penalty.
○ 11:59 PM May 28 ~ 11:59 PM May 29.
■ Late submission penalty (30%) will be applied to the total score.
○ After 11:59 PM May 29.
■ 100% penalty is applied for that submission.
● Your code will be automatically tested using an evaluation program.
○ Each problem has the maximum score.
○ A score will be assigned based on the behavior of the program.
● We won’t accept any submission via email - it will be ignored.
-1-
[CSED233-01] 2025 Spring, Data Structure, POSTECH PA #4
**** PLEASE READ THIS GRAY BOX CAREFULLY BEFORE STARTING THE ASSIGNMENT ****
Coding:
● Please do not use the containers in C++ standard template library (STL).
○ Such as <hash_set>, <queue>, <vector>, and <stack>.
○ Any submission using the above headers will be disregarded.
Submission:
● Compile your file(s) using C++ 11 compiler on ‘Replit’ or ‘Clion’ and check your
program before the submission
● All characters in [Link] should be in uppercase letters, e.g., ‘TRUE’, ‘FALSE’,
(except for [Task 1], [Task 2], …)
● Files you need to submit. (Do not change the filename.)
○ [Link]
○ [Link] and graph.h
Any questions?
● Please use PLMS - Q&A board. (Questions should be written in English and uploaded
publicly)
-2-
[CSED233-01] 2025 Spring, Data Structure, POSTECH PA #4
1. Undirected Graph – Second Shortest Path (3 pts)
a. Implement a function that returns the “Second shortest path” between node ‘A’ to ‘Z’
in the given undirected graph.
b. The ‘Second shortest path’ is defined as the shortest path from A to Z that does not
include any edge from any of the shortest paths. Some test cases may have multiple
shortest paths, and the second shortest path must be strictly longer than all of them.
c. The given graph is a simple undirected graph, meaning it contains no more than one
edge between any two nodes and no self-loops. The graph will always include node “A”
(the start node) and node “Z” (the destination node). All paths mentioned in this
problem (including the shortest and second shortest paths) refer to paths from A to Z.
You can modify [Link] and graph.h files for this problem.
d. All testcase shows only one valid “Second shortest path” or “NO PATH”
e. Input & Output
Input: Pairs of nodes with integer labels that indicate edges.
(A,B): an edge between node A and node B. The names of the nodes are
restricted to uppercase alphabetic characters.
Output:
If there is a ‘second shortest path’, print the path, including all visited nodes.
If not, print ‘NO PATH’
f. Example Input & Output
Input Output
"[('A','B'),('A','C'),('B','Z'),('C','D'),('D','Z')]" ACDZ
"[('A','B'), ('A','C'), ('C','Z')]" NO PATH
"[('A','B'),('B','C'),('C','Z'),('A','E'),('E','Z'), ABCZ
-3-
[CSED233-01] 2025 Spring, Data Structure, POSTECH PA #4
('A','F'), ('F','Z'), ('A','G'), ('G', 'Z')]"
g. Example execution
>> ./[Link] 1
"[('A','B'),('A','C'),('B','Z'),('C','D'),('D','Z')]"
[Task 1]
ACDZ
2. Directed Graph – Topological Sort (2 pts)
a. Implement a function that performs a topological sort using the given directed graph. If
there exists more than one result, print the topological sort that comes first in the
ascending order. To take an example below, acceptable topological sorts are ‘A B C D
F E’, ‘A C B F E D’, ‘A C D B F E’, etc. Among these, the desirable output
is ‘A B C D F E’. Also, print ‘ERROR’ if the topological sort could not be
performed. You can modify [Link] and graph.h files for this problem.
* You do not have to think about self loop cases. We will not put such case in our test
case.
b. Input & output
Input: Pairs of node labels that indicate edges.
('A','B'): an edge from node A to node B. All node names are single
uppercase alphabetic characters (A-Z).
If the input edge already exists in the graph, ignore the input.
Output:
Result of topological sort or ‘ERROR’ message
c. Example Input & Output
-4-
[CSED233-01] 2025 Spring, Data Structure, POSTECH PA #4
Input Output
"[('A','B'),('A','C'),('B','F'),('F',' A B C D F E
E'),('C','E'),('C','D')]"
"[('A','B'), ('A','D'), ('B','C'), ('C','E'), A B C D E F
('D','E'), ('E','F')]"
"[('B','C'), ('C','D'), ('D','B')]" ERROR
d. Example execution
>> ./[Link] 2 “[('A','B'),('A','C'),('B','F'),('F','
E'),('C','E'),('C','D')]”
[Task 2]
A B C D F E
3. Directed Graph – Strongly Connected Components (2 pts)
a. Implement a function that returns the strongly connected in the given directed graph.
We show an example below. You can modify [Link] and graph.h and [Link] files
for this problem.
b. Input & output
Input: Pairs of node labels that indicate edges.
('A','B'): an edge from node A to node B. All node names are single
uppercase alphabetic characters (A-Z).
If the input edge already exists in the graph, ignore the input.
Output:
Each strongly connected component should be printed on a new line.
Within each component, the nodes should be sorted in alphabetical
(ascending) order.
After that, the list of components should also be sorted based on the first
node of each component (in alphabetical order).
Check the (c) and (d)
-5-
[CSED233-01] 2025 Spring, Data Structure, POSTECH PA #4
c. Example Input & Output
The input and output of such graph is written in the first row.
Input Output
"[('A','B'),('B','C'),('C','A'),('D','B A B C
'),('D','E'),('F','E'),('G','F'),('E','G')]" D
E F G
"[('A','B'), ('B','C'), ('A','C')]" A
B
C
"[('A','B'), ('B','C'), ('C','A')]" A B C
"[('A','B'), ('B','C'), ('A','C'), ('D','E'), A
('E','F'), ('F','D')]" B
C
D E F
d. Example execution
>> ./[Link] 3 "[('A','F'), ('C','A'), ('F','C'), ('C','E'),
('E','D'), ('D','B'), ('B','G'), ('G','D')]"
[Task 3]
A C F
B D G
E
-6-
[CSED233-01] 2025 Spring, Data Structure, POSTECH PA #4
4. Reachable Node Count within Budget- Dikjstra’s Algorithm (4 pts)
a. Implement a function that performs the following steps:
i. From the given source node, compute the shortest path cost to all other nodes
using Dijkstra’s algorithm.
ii. Count how many destination nodes are reachable from the source such that the
total cost (sum of the weights of the edges along the path) does not exceed the
given budget.
iii. Return the number of such reachable nodes (excluding the source node itself).
b. The given graph is assumed to be directed, weighted, and weakly-connected.
c. All edge weights are positive integers greater than 0.
d. If no nodes are reachable from the source within the budget, return 0.
e. The maximum number of nodes in the graph is 26 (A to Z), without considering
duplicate nodes.
f. You can modify [Link] and graph.h files for this problem.
g. Input & Output
Input: A sequence of commands
-7-
[CSED233-01] 2025 Spring, Data Structure, POSTECH PA #4
(‘A-B’, integer): an edge from node ‘A’ to node ‘B’ with a weight value
{integer}. You don’t need to consider duplicate edges or self-directed edges
(i.e., edges from a node to itself). The input will not contain such cases.
(‘A’, integer) : the first element is the source node, and the second integer is
the maximum allowed cost (budget).
Output:
A single integer indicating the number of destination nodes that can be
reached from the source node with a total path cost less than or equal to the
budget.
The output should include only the number (e.g., 3) followed by a newline
character.
If no node is reachable, print 0.
h. Example input & output
Input Output
"[('A-B',10),('A-C',3),('B-D',5),('C-B',2), 3
('C-E',15),('A-D',20),('D-E',11),('A',11)]"
"[('A-B',10),('A-C',3),('B-D',5),('C-B',2), 1
('C-E',15),('A-D',20),('D-E',11),('A',4)]"
"[('A-B',10),('A-C',3),('B-D',5),('C-B',2), 0
('C-E',15),('A-D',20),('D-E',11),('A',2)]"
"[('A-B',10),('A-C',3),('B-D',5),('C-B',2), 1
('C-E',15),('A-D',20),('D-E',11),('D',12)]"
i. Example execution
>> ./[Link] 4 "[('A-B',10),('A-C',3),('B-D',5),('C-B',2),
('C-E',15),('A-D',20),('D-E',11),('A',11)]"
[Task 4]
3
-8-
[CSED233-01] 2025 Spring, Data Structure, POSTECH PA #4
5. Maximum-Cost Spanning Tree with Edge Constraints (4 pts)
a. Design a function that constructs the Maximum-Cost Spanning Tree (MaST) from a given
undirected, weighted graph using Kruskal’s algorithm. Some edges are explicitly marked
as required or forbidden, and your implementation must honor these constraints when
building the tree.
b. While the tree is being built, your function should output each selected edge and its
weight. Finally, return the total cost (sum of edge weights) of the MaST.
c. Although edges like ('A-B') and ('B-A') represent the same undirected edge, for sorting
and printing purposes, we always store and compare them in lexicographical order, i.e.,
the node with the smaller label comes first. So, all edges are internally represented as
('A-B') (not ('B-A')) if 'A' < 'B'.
d. Edges must be printed in lexicographical order (e.g., A B instead of B A), and when
multiple edges have the same weight, they should be selected in lexicographical order
by comparing node labels. Edge comparison example: ('A-C', 3) > ('A-B', 3) > ('A-C', 2)
e. Graph and Constraints
The input graph is undirected and guaranteed to be connected.
All edge weights are positive integers between 1 and 100.
Edges marked with:
0: must be included in the MaST
-1: must be excluded from the MaST
{positive weight}: regular edge, may be used
The tree must respect inclusion and exclusion constraints at all times.
.
f. Input & Output
Input: A list of tuples in the following format:
('A-B', integer): an edge between node A and node B with a weight
value of {integer}.
(‘A-B’, -1): a forbidden edge (must not be included)
(‘A-B’, 0): a required edge (must be included)
('MST', NULL): find MST using Kruskal's algorithm.
-9-
[CSED233-01] 2025 Spring, Data Structure, POSTECH PA #4
All node names are uppercase letters (A-Z). you do not need to handle duplicate or self-
loop edges.
Output:
Each time the MaST grows, print: [Node 1] [Node 2] … [Weight] where [Node
1] and [Node 2] are sorted lexicographically.
After all edges are selected, print the total cost of the MaST as a single
integer on the last line.
g. Example input & output
Input Output
“[('D-B', 1), ('D-C', 2), ('E-D', 5), ('B-A', 3), D E 5
('C-A', 1), ('C-B', 4), ('B-D', -1), ('MST', NULL)]” B C 4
A B 3
C D 2
14
“[('A-B', 3), ('B-C', 2), ('C-D', 5), ('A-D', 4), C D 5
('MST', None)]” A D 4
A B 3
12
“[('A-B', 3), ('B-C', 2), ('C-D', 5), ('A-D', 4), A D 4
('C-D', -1), ('MST', None)]” A B 3
B C 2
9
“[('A-B', 3), ('B-C', 2), ('C-D', 5), ('A-D', 4), C D 5
('A-B', 0), ('MST', None)]” A D 4
A B 3
12
h. Example execution
>> ./[Link] 5 "[('D-B',1),('D-C',2),('E-D',5),('B-A',3),('C-
A',1),('C-B',4),('B-D',-1),('MST',NULL)]"
[Task 5]
D E 5
B C 4
A B 3
C D 2
14
i. Notes & Clarifications
-10-
[CSED233-01] 2025 Spring, Data Structure, POSTECH PA #4
Always select the edge with the highest weight available.
If multiple edges share the same weight, choose based on lexicographical order
of the node labels.
Do not count duplicate or self-loop edges – they will not appear in the input.
Nodes range from ‘A’ to ‘Z’. The maximum number of nodes is 26.
-11-