Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
60321 | xyh2022 | J4 | C++ | 通过 | 100 | 347 MS | 35496 KB | 889 | 2022-10-15 11:25:24 |
#include<bits/stdc++.h> using namespace std; const int N=2e6+10; struct node{ int to,nxt; }edge[N]; int n,m,head[N],tot; int rd[N],tp[N],ans; queue<int> q; void add(int u,int v){ edge[++tot].to=v; edge[tot].nxt=head[u]; head[u]=tot; } int main(){ //freopen("J4.in","r",stdin); //freopen("J4.out","w",stdout); scanf("%d%d",&n,&m); for(register int i=1;i<=m;i++){ int u,v; scanf("%d%d",&u,&v); add(u,v); rd[v]++; } for(register int i=1;i<=n;i++){ if(!rd[i]) q.push(i); tp[i]=1; //printf("%d ",rd[i]); } while(!q.empty()){ int u=q.front(); q.pop(); for(register int i=head[u];i;i=edge[i].nxt){ int v=edge[i].to; tp[v]=tp[u]+1; rd[v]--; if(!rd[v]) q.push(v); } } for(register int i=1;i<=n;i++) if(tp[i]==1||tp[i]==2) ans++; printf("%d\n",ans); return 0; } /* 5 6 2 1 5 1 2 3 4 3 5 4 4 1 */