建反图,跑一个拓扑排序dp即可.

Code:

#include <bits/stdc++.h>
#define ll long long
#define N 100005
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
ll f[N];
queue<int>q;
int edges,n,m;
int in[N],out[N],hd[N],to[N<<1],nex[N<<1],mk[N];
void add(int u,int v)
{
nex[++edges]=hd[u],hd[u]=edges,to[edges]=v;
}
int main()
{
int i,j;
// setIO("input");
scanf("%d%d",&n,&m);
for(i=1;i<=m;++i)
{
int a,b;
scanf("%d%d",&a,&b),add(b,a),++in[a],++out[b];
}
for(i=1;i<=n;++i)
{
if(in[i]==0 && out[i]!=0)
{
q.push(i),f[i]=1,mk[i]=1;
}
}
for(;!q.empty();)
{
int u=q.front();q.pop();
for(int i=hd[u];i;i=nex[i])
{
int v=to[i];
f[v]+=f[u];
--in[v];
if(in[v]==0) q.push(v);
}
}
ll ans=0;
for(i=1;i<=n;++i)
{
if(out[i]==0 && !mk[i])
{
ans+=f[i];
}
}
printf("%lld\n",ans);
return 0;
}

  

最新文章

  1. html5 Worker学习
  2. 职责链模式(chain of responsibility Pattern)
  3. Zabbix3.0 自动邮件报障
  4. jquery mobile 请求数据方法执行时显示加载中提示框
  5. SVN中的常见错误(长期更新)
  6. PHP中$_REQUEST中包含的数据,数据被覆盖问题
  7. printf, fprintf, sprintf, snprintf, vprintf, vfprintf, vsprintf, vsnprintf - 输出格式转换函数
  8. ios 获取字符串所需要占用的label的高度
  9. BJUI 转
  10. contextmenu
  11. MVC 4 插件化架构简单实现
  12. linux 进程命令
  13. centos docker 安装
  14. JS模块化:CommonJS和AMD(Require.js)
  15. 案例:通过shell脚本实现mysql数据备份与清理
  16. dll多个版本问题
  17. codevs 1004 四子连棋 BFS、hash判重
  18. LNMP redis 安装、PHPredis扩展配置、服务器自启动、redis认证密码
  19. plsql的快速生成sql语句设置
  20. http协议与https协议的区别

热门文章

  1. Go-函数高级使用-条件分支-包管理-for循环-switch语句-数组及切片-与或非逻辑符
  2. QAbstractItemModel使用样例与解析(Model::index使用了createIndex,它会被销毁吗?被销毁了,因为栈对象出了括号就会被销毁)
  3. 牛客 201 J Princess Principal (括号, 栈模拟)
  4. 01 Java 内存分配全面浅析
  5. Hash一致性算法底层原理
  6. JavaScript 的编译原理
  7. 不显示Zetero导出的文献库中的部分内容
  8. C# Winfrom 自定义控件添加图标
  9. Centos7 docker、harbor 安装配置
  10. delphi Tidhttp 发送json格式报文