15-295 Reading 5 (Wednesday, February 16, 2005)
Assigned Readings
-
First edition: Sections 23.1-23.4
-
Second edition: Sections 22.1-22.4
Problem A: Coffee machines
A university campus includes several buildings, some of which are connected
by corridors; two buildings may have at most one corridor between them,
which means that the corridors form a well-defined undirected graph. The
university administration has decided to install new coffee machines throughout
the campus, in such a way that students can always get coffee without going
outside the buildings. Thus, if several buildings are connected by corridors,
they need only one coffee machine; on the other hand, if two buildings
are not connected by any chain of corridors, they require two different
machines. Your task is to write a program that determines the minimal required
number of machines.
Input
The first line contains a positive integer n between 1 and 100,000,
which is the number of buildings; the other lines describe corridors between
buildings, one corridor per line. The description of a corridor includes
two distinct integers between 1 and n, separated by a single space,
which represent the buildings connected by this corridor; for example,
the line "2 4" describes a corridor between buildings 2 and 4. The total
number of corridors is at most 1,000,000; the last line is "0 0", which
does not represent a corridor.
Output
The output is a single integer number, which represents the minimal required
number of coffee machines.
Sample input
6
1 2
2 3
4 5
0 0
Sample output
3
Problem B: Counterintelligence
The country of Big Endians is at war with the neighboring country of Little
Endians, and the Big-Endian police has recently discovered a network of
Little-Endian spies. Since the Big-Endian police intercepts phone and e-mail
communications, the spies use pigeons to deliver sensitive information.
This strategy helped them to remain undetected for a long time, but eventually
the police has mapped all pigeon routes. Each route is a one-way communication
channel between two spies, which means that these routes form a directed
graph. The police believes that the network may include a spymaster, who
collects information from all other spies and never sends anything back;
that is, every spy has a direct pigeon route to the spymaster, whereas
the spymaster does not send pigeons to anyone. Your task is to write a
program that helps the police to identify the spymaster.
Input
The first line contains a positive integer n between 1 and 100,000,
which is the number of spies; the other lines describe pigeon routes, one
route per line. The description of a route includes two distinct integers
between 1 and n, separated by a single space; the first integer
is the spy sending a pigeon, and the second is the receiving spy. The total
number of pigeon routes is at most 1,000,000; the last line is "0 0", which
does not represent a route.
Output
If the network includes a spymaster, the output is a single integer number,
which represents the spymaster; else, the output is the string "No spymaster."
Sample input
4
1 2
1 3
3 1
3 2
4 1
4 2
4 3
0 0
Sample output
2
Problem C: Odd artwork
The modern art sometimes looks strange, and critics may disagree whether
a specific abstract sculpture is a true piece of art, or just a pile of
broken appliances. A famous abstract artist has recently presented a new
controversial sculpture; it consists of small rubber balls, connected by
wires, which form a complex undirected graph in three dimensions. The artist
claims that this graph does not have cycles with odd number of edges, and
that its main artistic value is the absence of such cycles. Since this
structure includes a huge number of balls and wires, critics cannot verify
the absence of odd-length cycles, and they are skeptical about the artist's
claim. Your task is to write a program that checks whether the artist is
right.
Input
The first line contains a positive integer n between 1 and 100,000,
which is the number of rubber balls; the other lines describe wires, one
wire per line. The description of a wire includes two distinct integers
between 1 and n, separated by a single space, which represent the
balls connected by this wire. The total number of balls is at most 1,000,000;
the last line is "0 0", which does not represent a wire.
Output
If the sculpture has no cycles with an odd number of edges, the output
is "The artist is right"; else, it is "The artist is wrong".
Example input
6
1 2
1 3
2 4
3 4
3 5
4 6
5 6
0 0
Example output
The artist is right