
CS 302 Assignment 5:
Computing the Components of a Graph Using Union/Find
Due date: Monday, October 31, 2015, midnight.
All programming assignments must be
submitted electronically.
Submit them to the graduate assistant by email on or before the due date at
Your email must come from your engineering college (or computer science
or computer engineering) account.
Your program must compile on the College of Engineering
machines.
-
Your program must read in a graph which is presented as a list of edges.
Vertices are the integers from 1 to n, and each edge is a pair of numbers
in the range 1 . . . n.
For example, the file in01 looks like this:
-
5
2 4
3 2
1 5
-
meaning that the graph has vertices 1, 2, 3, 4, 5, and edges
(2,4), (3,2), and (1,5).
-
Ignore self-loops and duplicate edges. For example, the file in02 has
the line 30 30, as well as several pairs of identical lines.
-
Here are the links to four input files and the four output files computed
by my program, as well as a link to a much larger file where I don't give the
output.
-
in01
out01
in02
out02
in03
out03
in04
out04
in06