分析:直接k次dfs,设一个cnt[i]表示第i个点被经过的次数,那么明显,cnt[i]=k时这个点是可以的。。
#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; int n,m; const int N=1e5+5; int tot,head[N],next[N],go[N],d[N],bz[N],k; inline void add(int x,int y) { go[++tot]=y; next[tot]=head[x]; head[x]=tot; } int vis[1005]; int cnt[N]; inline void dfs(int x) { vis[x]=1; cnt[x]++; int i=head[x]; while (i) { int v=go[i]; if (!vis[v]) { dfs(v); } i=next[i]; } } int main() { scanf("%d%d%d",&k,&n,&m); memset(bz,0,sizeof(bz)); fo(i,1,k)scanf("%d",&d[i]),bz[d[i]]=1; fo(i,1,m) { int x,y; scanf("%d%d",&x,&y); add(x,y); } int ans=0; fo(i,1,k) { memset(vis,0,sizeof(vis)); dfs(d[i]); //if (cnt==k-1)ans++; } fo(i,1,n) if (cnt[i]==k)ans++; printf("%d\n",ans); return 0; }