COMP20007 DESIGN OF ALGORITHMS Assignment 2
1 + 2 + 2 + 2 + 1 + 2 + 2 = 12 Marks
Australia faces one of its biggest disasters: a total power outage that lasted for a few minutes.
You are the CTO for the National Super Network (NSN). NSN is responsible for Australia’s
Internet backbone and connects all key Internet servers in Australia. After the blackout you
decide that it is best to ascertain the consequences of the power outage.
NSN has built its high-speed network so that
• all server connections are bi-directional;
• any two servers are connected if they share an edge or each of themhas a path to a shared
• the network can have subnetworks.
If everything is working well, all servers in a subnetwork are connected. Fortunately, each
server can be directly contacted through a slow telephone connection. You need to develop an
algorithm that determines the number of connected components in the network.
Develop the pseudocode for an efﬁcient algorithm that computes the number of connected
components in a graph G = (V, E) given vertices V and edges E. Discuss the complexity of
your algorithm in detail.
Write a C program that takes the name of one ﬁle as a command line argument containing
the speciﬁcation for the network, reads in a text ﬁle from standard input and prints out the
total number of connected subnetworks before the outage for this network. Suppose that the
network has n servers and each server has a unique server ID (SID)which is an integer between
0 and n 1 inclusively.
The ﬁle speciﬁed as the command line argument for this and the subsequent programming
tasks has two parts:
• The ﬁrst line gives the number of servers, n, and the number of network connections in
the graph, m, separated by a space.
• The following lines specify the m connections between servers, one per line, given as the
two SIDs separated by a space. Note that each edge is listed only once.
The text ﬁle received on standard input is also given in two parts:
• The ﬁrst line speciﬁes the number of servers which are affected by the outage.
• The following line contains a list of all the SIDs affected by the outage, each separated by
An example input text ﬁle (network-1.txt) is given below. The network conﬁguration before
the power outage is demonstrated in the following ﬁgure.
All four provided network test cases are shown at the end of the document.
You can assume that the text ﬁles used to test your program will be always sensible and cor-
rect. You do not need to perform any data validation. You can assume that a connection
between any pair of servers appears only once in the list. You can also assume the source and
destination server of a connection is always different.
An example of the text ﬁle sent in through standard input (outage-1.txt) is:
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: firstname.lastname@example.org 微信:itcsdx