1 条题解
-
1
#include<iostream> #include<cstdio> #include<queue> using namespace std; #define JYY return #define AK 0 #define IOI ; const int M=1e5+5,N=1e3+5; int n,m,D,tot=0,a[M],in[M],first[M]; bool vis[M],truth[M]; struct Edge{ int to,nxt,pd; }e[M<<1]; queue<int> Q; int read(){ int x=0,y=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') y=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); } return x*y; } void add(int x,int y,int fx){ e[++tot].nxt=first[x]; first[x]=tot; e[tot].to=y; e[tot].pd=fx; } bool check(int x){ for(int i=1;i<=n;i++) vis[i]=0;vis[x]=1; while(!Q.empty()) Q.pop();Q.push(x); while(!Q.empty()){ int u=Q.front();Q.pop(); for(int i=first[u];i;i=e[i].nxt){ int v=e[i].to; if(!e[i].pd) continue; if(truth[v]) return 1; if(!vis[v]) Q.push(v),vis[v]=1; } } for(int i=1;i<=n;i++) if(!in[i]&&!vis[i]) Q.push(i),vis[i]=1; while(!Q.empty()){ int u=Q.front();Q.pop(); for(int i=first[u];i;i=e[i].nxt){ int v=e[i].to; if(e[i].pd) continue; if(!vis[v]) Q.push(v),vis[v]=1; } } for(int i=1;i<=D;i++) if(!vis[a[i]]) return 1; return 0; } int main(){ n=read(),m=read(),D=read(); for(int i=1;i<=m;i++){ int x=read(),y=read(); add(x,y,0),add(y,x,1);in[y]++; } for(int i=1;i<=D;i++) a[i]=read(),truth[a[i]]=1; for(int i=1;i<=n;i++) if(truth[i]||check(i)) printf("%d ",i),truth[a[++D]=i]=1; printf("\n"); JYY AK IOI }
- 1
信息
- ID
- 4478
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 23
- 已通过
- 3
- 上传者