根据题目输入可以得到一个有向图

信号可以根据有向图的传递性传递,因此可以说是找到这个有向图的所有父亲即可

但又要考虑可能会出现环这类情况

所以跑一遍强连通分量模板,再根据分块后的图找到入度为0的块,把这些块当作信号发出源,就可以使全图都能够收到信号

所以答案就是入度为0的块的数量

(因为跑完程序刚好卡了时间限制,所以使用了缓冲区读入优化,最终程序耗时78ms)

#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
const int N=;
vector<int> G[N];
stack<int> S;
int pre[N],lowlink[N],sccno[N],dfs_clock,scc_cnt,ind[N];
const int bsz=<<;
char bf[bsz],*head,*tail;
inline char gc(){
if(head==tail){
int l=fread(bf,,bsz,stdin);
tail=(head=bf)+l;
}
return *head++;
}
inline int read(){
int x=;char c=gc();
while(!isdigit(c))c=gc();
for(;isdigit(c);c=gc())x=x*+c-'';
return x;
}
inline void write(int x){
if(x>=)write(x/);
putchar(x%+'');
}
void dfs(int in){
pre[in]=lowlink[in]=++dfs_clock;
S.push(in);
int num=G[in].size();
for(int i=;i<num;i++){
int v=G[in][i];
if(!pre[v]){
dfs(v);
lowlink[in]=min(lowlink[in],lowlink[v]);
}
else if(!sccno[v])
lowlink[in]=min(lowlink[in],pre[v]);
}
if(lowlink[in]==pre[in]){
scc_cnt++;
while(){
int x=S.top();
S.pop();
sccno[x]=scc_cnt;
if(x==in)
break;
}
}
}
int main(){
int N=read(),M=read(),i,j,a,b;
for(i=;i<M;i++){
a=read();
b=read();
G[a].push_back(b);
}
dfs_clock=scc_cnt=;
memset(sccno,,sizeof sccno);
memset(pre,,sizeof pre);
for(i=;i<=N;i++)
if(!pre[i])
dfs(i);
memset(ind,,sizeof ind);
for(i=;i<=N;i++){
a=G[i].size();
for(j=;j<a;j++)
if(sccno[i]!=sccno[G[i][j]])
ind[sccno[G[i][j]]]++;
}
for(a=,i=;i<=scc_cnt;i++)
if(!ind[i])
a++;
write(a); return ;
}

最新文章

  1. Apache2.4卡住无法访问的解决……
  2. 解决读取iphone名称中文乱码问题
  3. HTML 或 CSS 文件中引用的图片文件移动到任意位置
  4. Web API:将FlexChart导出为图片
  5. 移动端网页 -- 安卓与IOS兼容
  6. 修改dll版本号处理未能加载“******”,或找不到动态链接库依赖的项
  7. UVa 11300 Spreading the Wealth 分金币
  8. nginx+keepalived+tomcat之tomcat性能调优
  9. PHP简洁之道
  10. Oracle12c(12.1)中性能优化&amp;amp;功能增强之通过参数THREADED_EXECTION使用多线程模型
  11. kubernetes 基础一
  12. 64位ubuntu搭建android开发环境问题解决方案
  13. 【Windows】创建任务计划
  14. 由table理解display:table-cell
  15. 分布式系统的Raft算法
  16. django--用户认证组件
  17. 【异常】IOException parsing XML document from class path resource [xxx.xml]
  18. Gradle with Android
  19. python 模拟普通用户和管路员登录购物系统小程序
  20. UVA-11761-马尔可夫/记忆化搜索

热门文章

  1. DataGridView在HeaderCell显示行号
  2. ..\EEP\EEP.c(249): error: #268: declaration may not appear after executable statement in block
  3. Charles中windows版本解决response乱码问题
  4. 浅谈__slots__
  5. 当spring单元测试需要用到临时表的时候
  6. Spring Boot without the web server
  7. 2020PHP面试-SQL篇
  8. 在linux上部署多个tomcat
  9. @Autowired注解与@Resource注解的区别(详细)
  10. bash字符串处理