1 条题解
-
1
#include<bits/stdc++.h> using namespace std; void read(int &h){ char o; int x=0,y=1; o=getchar_unlocked(); while(!(o<='9'&&o>='0')){ if(o=='-'){ y=-1; } o=getchar_unlocked(); } while(o<='9'&&o>='0'){ x*=10; x+=o-'0'; o=getchar_unlocked(); } h=x*y; return ; } const int N=2e5+10; int n,m,dp[N],ind[N],u,v,cnt; vector<int> g[N]; queue<int> q; int main(){ ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr); read(n);read(m); for(int i=1;i<=m;i++){ read(u);read(v); ind[v]++; g[u].push_back(v); } for(int i=1;i<=n;i++){ if(!ind[i]&&g[i].size()){ q.push(i); dp[i]=1; } } while(!q.empty()){ int now=q.front(); q.pop(); if(!g[now].size()){ cnt+=dp[now]; } for(int it:g[now]){ dp[it]+=dp[now]; ind[it]--; if(!ind[it]){ q.push(it); } } } cout<<cnt; return 0; }
- 1
信息
- ID
- 7213
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 5
- 标签
- 递交数
- 7
- 已通过
- 5
- 上传者