We need to know which fields are reachable by all cows. Thus, it suffices to find the fields reachable by each cow. This can be achieved with either a breadth-first or depth-first walk over the edges starting from the initial cow, tagging visitable fields as one goes (a depth-first walk can be implemented with a simple recursion). This is O(K(N+M)), since each field and path is used at most once per cow.
An alternative solution is to use the Floyd-Warshall transitive-closure algorith, This is an extremely simple triple-loop that yields the transitive closure - that is, a table indicating whether there is a route from each field to each other field. If you are not familiar with this algorithm, you should look it up on the Internet. It is a handy tool in contests simply because it is very compact.
Floyd-Warshall is far slower at O(N^3), since it computes reachable sets for every field rather than every cow, and also does not benefit from relatively small number of paths. While O(N^3) is normally too slow for N=1000, the algorithm has an extremely tight inner loop and can be implemented using bit-sets that allow 32 bits to be manipulated at a time. This makes it practical to use in this situation.
#include <fstream> #include <algorithm> #include <bitset> using namespace std; typedef bitset<1000> vset; int main() { int K, N, M; ifstream in("picnic.in"); in >> K >> N >> M; int cows[K]; vset edges[N]; for (int i = 0; i < K; i++) { in >> cows[i]; cows[i]--; } for (int i = 0; i < M; i++) { int A, B; in >> A >> B; A--; B--; edges[A].set(B); } for (int i = 0; i < N; i++) edges[i].set(i); for (int y = 0; y < N; y++) for (int x = 0; x < N; x++) if (edges[x].test(y)) edges[x] |= edges[y]; int ans = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < K; j++) if (!edges[cows[j]].test(i)) goto bad; ans++; bad:; } ofstream out("picnic.out"); out << ans << "\n"; }