洛谷P2853 [USACO06DEC] Cow Picnic S

题目链接：[USACO06DEC] Cow Picnic S - 洛谷、

题目描述：有 n 个牧场，编号从 1 到 n，每个牧场之间可能有通道。共有 k 只奶牛，每只奶牛位于一个特定的牧场。现在我们需要找到所有奶牛都能到达的牧场。对于每个牧场 i，如果所有 k 只奶牛都能到达该牧场，那么这个牧场就是一个有效的集会地点。

输入格式：

第一行：三个整数 K、N、M，分别表示奶牛的数量、牧场的数量和有向路径的数量。

接下来 K 行，每行一个整数，表示第 i 只奶牛所在的牧场编号。

接下来 M 行，每行两个整数 A 和 B (1 ≤ A, B ≤ N, A ≠ B)，表示从牧场 A 到牧场 B 有一条有向路径。

输出格式

输出一个整数，表示所有奶牛都能通过有向路径到达的牧场数量。

解题思路：从k个奶牛分别dfs只有s[i] = k 时候才让ans + 1，图用邻接矩阵才存储。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 10010; 
int g[N][N];
int cow[N],s[N];
bool vis[N];

int k,n,m; 
int ans;

int read()
{
    int t = 0, f = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch <= '9' && ch >= '0') {
        t = t * 10 + ch - '0';
        ch = getchar();
    }
    return t * f;
} 

void dfs(int x)
{
	vis[x] = true;
	s[x]++;
	for(int i = 1; i <= n; i++)
	{
		if(!vis[i] && g[x][i]) dfs(i);
	}
}

int main() 
{
   
   k = read(),n = read(),m = read();
   
   for(int i = 1; i <= k; i++)  cow[i] = read();
   
   while(m--)
   {
   	 int u = read(),v = read();
   	 g[u][v] = 1;
   }
   
   for(int i = 1; i <= n; i++)
   {
   	  dfs(cow[i]);
   	  memset(vis,false,sizeof(vis));
   }
    
   for(int i = 1; i <= n; i++) 
   {
   	  if(s[i] == k) ans ++;
   }
   
   cout<<ans;
   
   return 0;
}