首页 > 代码库 > BZOJ 4562 搜索...
BZOJ 4562 搜索...
思路:
统计入度&出度
每搜到一个点
in[v[i]]--,f[v[i]]+=f[t]; if(!in[v[i]])if(out[v[i]])q.push(v[i]);else ans+=f[v[i]];
//By SiriusRen#include <queue>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N=200050;int n,m,xx,yy,v[N],next[N],first[N],tot,f[N],in[N],out[N],ans;void add(int x,int y){v[tot]=y,next[tot]=first[x],first[x]=tot++;}queue<int>q;int main(){ memset(first,-1,sizeof(first)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d",&xx,&yy); add(xx,yy);in[yy]++,out[xx]++; } for(int i=1;i<=n;i++)if(!in[i])q.push(i),f[i]=1; while(!q.empty()){ int t=q.front();q.pop(); for(int i=first[t];~i;i=next[i]){ in[v[i]]--,f[v[i]]+=f[t]; if(!in[v[i]])if(out[v[i]])q.push(v[i]);else ans+=f[v[i]]; } } printf("%d\n",ans);}
BZOJ 4562 搜索...
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。