피크닉

문제

소들은 피크닉을 갈 예정이다! 각 존의 K(1 <= K <= 100)마리의 소들은 N(1 <= N <= 1,000) 개의 목초지중 하나의 목초지에서 풀을 뜯고 있다. 이 목초지들을 목초지1 … 목초지 N이라고 명명하자. 그 목초지들은 M (1 <= M <= 10,000) 개의 단방향 길로 연결되어 있다. (어떠한 길도 출발지와 도착지가 같지 않다.)

소들은 그들의 피크닉동안 같은 목초지에서 모이기를 원한다. 하지만 몇마리의 소들은 모든 목초지에 도달할 수 없을 가능성이 있다.(단방향 도로이기 때문에) 소들을 도와 얼마나 많은 목초지에서 모든 소들이 모일 수 있는지 계산해주자.

---

입력

첫번째 줄은 세개의 정수가 공백으로 구분되어 입력되어진다. :K,N,M

2번째줄부터 K+1번째 줄까지는 K마리의 소들의 처음 풀을 뜯고있는 위치가 각 줄에 하나씩 주어진다.

K+2번째 줄부터 M+K+1번째 줄까지는 단방향 도로의 정보 시작점S 와 끝점E가 입력으로 주어진다.

---

출력

모든 소가 모일 수 있는 가능한 목초지의 수를 출력해주자

---

힌트

예제 입력

2 4 4

2

3

1 2

1 4

2 3

3 4

예제 출력

2

힌트

모든 소들은 목초지 3,4에서 모일 수 있다.

#include <iostream> #include <fstream> #include <vector> #include <queue> using namespace std; int K, N, M; vector<int> pathV[1001]; int cow[101]; int totalVisit[1001]; void BFS(int start) { queue<int> visitQ; visitQ.push(start); int visit[1001]; for (int i = 1; i <= 1000; i++) { visit[i] = 0; } visit[start] = 1; while (!visitQ.empty()) { int num = visitQ.front(); totalVisit[num] += 1; visitQ.pop(); vector<int>::iterator iter; for (iter = pathV[num].begin(); iter != pathV[num].end(); iter++) { int next = *iter; if (visit[next] == 0) { visit[next] = 1; visitQ.push(next); } } } } int main() { cin >> K >> N >> M; for (int k = 1; k <= K; k++) { cin >> cow[k];//소의 위치 } int s, e; for (int m = 1; m <= M; m++) { cin >> s >> e; pathV[s].push_back(e); } for (int k = 1; k <= K; k++) { BFS(cow[k]); } int cnt = 0; for (int i = 1; i <= N; i++) { if (totalVisit[i] == K) { cnt++; } } cout << cnt << endl; return 0; }