문제
소들은 피크닉을 갈 예정이다! 각 존의 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에서 모일 수 있다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | #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;} |