Drug Investigation Unit
InterviewTime limit1sMemory limit256 MB
Given a directed supply graph and a set of arrested suppliers, count how many remaining suppliers still receive drugs from some origin.
- Level
Medium5 of 10
- Topics
- Graph, DFS, Implementation, Queue
- Solved
- No attempts yet
Problem
Social problems related to drugs have been occurring frequently around the world lately. In response, the police want to block drug distribution as much as the limited manpower of the drug investigation unit allows.
Drug suppliers obtain drugs from one another. The drug investigation unit has recently identified part of the network among the drug suppliers. This network can be represented as a graph. Each node is a drug supplier, and each edge represents a supply relation. For example, the graph below shows the following.
- Drug supplier A supplies drugs to drug suppliers B, C, D, and E.
- Drug supplier F obtains drugs from B and C, then supplies them to I.
- I supplies J, J supplies K, D supplies G, and E supplies H.

The drug investigation unit can arrest drug suppliers whose whereabouts it has identified.
For example, even if the unit arrests B and C, D, E, G, and H can still obtain drugs.
The origin of drugs is a drug supplier that supplies drugs without obtaining any from another supplier.
Given information about the network among drug suppliers and the drug suppliers arrested by the unit, write a program that finds the number of drug suppliers that can still obtain drugs.
Input
The first line gives the number of drug suppliers and the number of relations among drug suppliers . Each drug supplier is represented by an uppercase letter, starting with A in order.
From the second line, lines give the relations among the drug suppliers. (A B : A -> B)
The last line gives the number of drug suppliers whose whereabouts the police have identified, followed by each identified drug supplier, separated by spaces.
Output
Output the number of drug suppliers that can still obtain drugs after the drug investigation unit arrests the identified drug suppliers.