社区讨论
在线IDE炸了,挂掉60分,求助
P4017最大食物链计数参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lo2tewfz
- 此快照首次捕获于
- 2023/10/23 19:29 2 年前
- 此快照最后确认于
- 2023/10/23 19:29 2 年前
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,ans;
queue<int> q;
vector<int> g[5010];
int rd[5010];
int cd[5010];
int cnt[5010];
inline int read(){
int x=0;
char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+c-48;
c=getchar();
}
return x;
}
void topsort(){
while(!q.empty()){
int t=q.front();
q.pop();
for(int i=0;i<g[t].size();++i){
int j=g[t][i];
--rd[j];
cnt[j]=(cnt[j]+cnt[t])%80112002;
if(rd[j]==0) q.push(j);
}
}
return;
}
signed main(){
n=read();m=read();
while(m--){
int u=read(),v=read();
g[u].push_back(v);
rd[v]++;cd[u]++;
}
for(int i=1;i<=n;++i){
if(rd[i]==0){
q.push(i);
cnt[i]=1;
}
}
topsort();
for(int i=1;i<=n;++i){
if(cd[i]==0) ans=(ans+cnt[i])%80112002;
}
cout<<ans;
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...