|Online Judge||Problem Set||Authors||Online Contests||User|
Power Cable Problem
The downtown of city T consists of N, 1 <= N <= 10000, tall commercial buildings that have basements. The buildings are numbered from 0 through N-1. The electricity of each building is provided by the City Electrical Power Company that puts all of its M, 1 <= M <= 50, power cables underground. In order for a building to have electricity, a power line must be connected from one of the underground cables to a power converter inside the building. Because of technical reasons, each power cable is a loop, meaning that it is a long cable line that originates from a mini power station, runs through some regions in the city and then comes back to the same power station. It is known that each power cable connects to at least 2 and at most 500 buildings. A building may be connected to zero, one or more than one power cable. The electricity of a building connected to more than one power cable can be provided by any one power cable by properly setting its power converter. To have a better city view, it is required by the law that power converters can only be built inside the basements.
During a Typhoon, the local rain storm, the downtown of city T is flooded. The basements of K, 1 <= K <= N, buildings are filled with water. Fortunately, none of the mini power stations are damaged. Once a basement is flooded with rain water, its power converter is damaged and the building is out of electricity. Before fixing the power converter, we need to drain the water in the basement, which takes at least a long time. To make the situation worse, the power cables of city T are designed with the constraint that for each power cable, if it is connected with a damaged power converter, then none of the power converters connected to this power cable can be turned on. It is also impossible to disconnect the damaged power converts from the power cables. However, it is possible to properly set a power convert to get electricity from a power cable that carries electricity. After Typhoon, the City Electrical Power Company needs to know the total number of buildings that are out of electricity. Since the flood has made the traffics inside the city bad, the company cannot send people to survey. Fortunately, it is known by the company the buildings that are flooded in Typhoon since people from those buildings telephoned the company for help. Giving the original power line connection oor plans and the buildings that are flooded, your task is to calculate the total number of buildings that are currently out of electricity, including the ones that are originally not connecting to any power cable.
For example, each circle in Figure 1 represents a building. Two concentric circles represents a flooded building. There are 9 buildings. Buildings 7 and 8 are flooded. Solid straight lines are power cables. There are 3 power cable lines. One connects buildings 0, 1 and 6. One connects buildings 1, 2, 3 and 7. The last one connects buildings 0, 1, 4, 5 and 8. Buildings 2, 3, 4, 5, 7 and 8 do not have electricity currently in this example.
The input file consists of several test cases. In each test case, the first line consists of three integers N, M and K separated by a single space. Each of the following M lines represents in a power cable by beginning with the number of buildings in this power cable and then a list of buildings in this cable in clockwise order. It then followed by a line of K integers, each separated by a space, representing the buildings that are flooded. A line with three 0's separates two test cases. The end of the file is a line with three -1's.
For each test case, output the total number of buildings that are out of electricity in a line.
9 3 2 3 0 1 6 4 1 7 3 2 5 0 4 5 8 1 7 8 0 0 0 5 2 1 3 0 2 1 3 1 4 3 4 -1 -1 -1
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator